首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。