首页 > 代码库 > UVA 257 - Palinwords(字符串HASH)

UVA 257 - Palinwords(字符串HASH)

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;
}