http://acm.hdu.edu.cn/showproblem.php?pid=4763
题目大意：给一个字符串，判断是否可以写成ABACA,B、C表示长度大于等于0的字符串。
方法：ans = next[len]如果小于等于len/3,则ans是最大可能的答案，否则ans = next[ans] 要继续往前走，直到ans <= len/3, 然后枚举从2*ans位置枚举到len - ans，看是否存在某个位置j, 使得next[j] = ans，当然这里也有一个往前走的过程（如果next[j]一开始大于ans），具体见代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <map> 7 #include <vector> 8 #include <stack> 9 #include <string> 10 #include <ctime> 11 #include <queue> 12 #define mem0(a) memset(a, 0, sizeof(a)) 13 #define mem(a, b) memset(a, b, sizeof(a)) 14 #define lson l, m, rt << 1 15 #define rson m + 1, r, rt << 1 | 1 16 #define eps 0.0000001 17 #define lowbit(x) ((x) & -(x)) 18 #define memc(a, b) memcpy(a, b, sizeof(b)) 19 #define x_x(a) ((a) * (a)) 20 #define LL long long 21 #define DB double 22 #define pi 3.14159265359 23 #define MD 10000007 24 #define INF (int)1e9 25 #define max(a, b) ((a) > (b)? (a) : (b)) 26 using namespace std; 27 char str[1200000]; 28 int next[1200000]; 29 void getNext() 30 { 31 next[0] = next[1] = 0; 32 for(int i = 1; str[i]; i++) { 33 int j = next[i]; 34 while(j && str[i] != str[j]) j = next[j]; 35 next[i + 1] = str[i] == str[j]? j + 1 : 0; 36 } 37 } 38 int solve() 39 { 40 int len = strlen(str), ans = next[len], F = 0; 41 while(ans * 3 > len) ans = next[ans]; 42 while(ans) { 43 for(int i = ans * 2; i <= len - ans; i++) { 44 int j = next[i]; 45 while(j > ans) j = next[j]; 46 if(j == ans) { 47 F = 1; 48 break; 49 } 50 } 51 if(F) break; 52 ans = next[ans]; 53 } 54 return ans; 55 } 56 int main() 57 { 58 //freopen("input.txt", "r", stdin); 59 int T; 60 cin>> T; 61 for(int i = 1; i <= T; i++) { 62 scanf("%s", str); 63 getNext(); 64 cout<< solve()<< endl; 65 } 66 return 0; 67 }