UVA 257 - Palinwords

题目链接

题意：输出一个文本里面的palinword，palinword的定义为。包括两个不同的回文子串，而且要求回文子串不能互相包括

思路：对于每一个单词推断一次。因为不能互相包括。对于每一个位置。事实上就仅仅要找长度3和4的情况就可以，这样复杂度为O(n)，至于推断反复的。就用hash就可以

代码：

#include <cstdio>

#include <cstring>

char str[260];

int hash[555555], save[260], sn;

bool check() {

    sn = 0;

    int n = strlen(str);

    for (int i = 1; i < n - 1; i++) {

	if (str[i - 1] == str[i + 1]) {

	    int num = (str[i - 1] - 'A' + 1) * 27 * 27 + (str[i] - 'A' + 1) * 27 + str[i + 1] - 'A' + 1;

	    if (!hash[num]) {

		hash[num] = 1;

		save[sn++] = num;

	    }

	    continue;

	}

	if (str[i] == str[i + 1] && str[i - 1] == str[i + 2]) {

	    int num = (str[i - 1] - 'A' + 1) * 27 * 27 * 27 + (str[i] - 'A' + 1) * 27 * 27 + (str[i + 1] - 'A' + 1) * 27 + str[i + 2] - 'A' + 1;

	    if (!hash[num]) {

		hash[num] = 1;

		save[sn++] = num;

	    }

	}

    }

    for (int i = 0; i < sn; i++)

	hash[save[i]] = 0;

    return sn >= 2;

}

int main() {

    while (~scanf("%s", str))

	if (check())

	    printf("%s\n", str);

    return 0;

}