Palinwords （处理回文串）

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdlib.h>
 5 #include <string>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 
14 
15 #define INF 0x3f3f3f3f
16 #define LL long long
17 
18 typedef unsigned long long ull;
19 const int maxn = 1e5+10;
20 
21 char s[maxn];
22 ull base = 131;
23 ull mod = 1e9+7;
24 ull p[maxn];
25 ull h1[maxn],h2[maxn];
26 ull q[maxn];
27 
28 
29 ull get_hash(ull h[],int l,int r){
30     return (h[r] - h[l-1]*p[r-l+1]);
31 }
32 
33 bool check(char s[]) {
34     std::set<ull> st;
35     int ans = 0;
36     int len = strlen(s+1);
37     for (int i=2;i+1<=len;i++) {
38         if (s[i-1] == s[i+1]) {
39             ull temp = get_hash(h1,i-1,i+1);
40             if (st.find(temp) == st.end()) {
41                 st.insert(temp);
42                 ans++;
43             }
44         }
45     }
46 
47     for (int i=1;i+3<=len;i++) {
48         if (s[i] == s[i+3] && s[i+1] == s[i+2]) {
49             ull a = get_hash(h1,i,i+3);
50             ull b = get_hash(h1,i+1,i+3);
51             ull c = get_hash(h1,i,i+2);
52             if (st.find(a) == st.end() && st.find(b) == st.end() && st.find(c) == st.end()) {
53                 ans++;
54                 st.insert(a);
55                 st.insert(b);
56                 st.insert(c);
57             }
58         }
59     }
60     return ans >= 2;
61 }
62 
63 int main() {
64     p[0] = 1;
65     for (int i=1;i<maxn;i++) {
66         p[i] = p[i-1] * base;
67     }
68     while (~scanf("%s",s+1)) {
69         int len = strlen(s+1);
70         for (int i=1;i<=len;i++) {
71             h1[i] = h1[i-1] * base + s[i];
72         }
73         if (check(s)) {
74             printf("%s\n",s+1);
75         }
76     }
77     return 0;
78 }