题意：求一个字符串中 前缀 和 后缀 相同的长度
分析： 对于一个字符串他自己的长度肯定是可以的。然后如果满足 前缀 和 后缀相等，那个前缀 最后一个字符 一定 和 该字符串最后一个字符相等，不然不会满足条件。
所以 找 str[len - 1] 的next数组， 对于 next[len - 1] 来看看这个位置 是不是等于最后一个字符，如果相等，那么前 next[len - 1] 一定是可以的， 然后 在判断next[ next[len - 1] ] 是不是等于 str[len - 1] .... 就是一层一层的往前找前缀，判断当前位置 是否等于 最后一个字符
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 using namespace std; 6 const int Max = 400000 + 10; 7 char str[Max]; 8 int Next[Max]; 9 int ans[Max]; 10 void getNext(int & len) 11 { 12 int i = 0, k = -1; 13 Next[0] = -1; 14 while (i < len) 15 { 16 while (k != -1 && str[k] != str[i]) 17 k = Next[k]; 18 Next[++i] = ++k; 19 } 20 } 21 int main() 22 { 23 while (scanf("%s", str) != EOF) 24 { 25 int len =strlen(str); 26 getNext(len); 27 int cnt = 0; 28 ans[cnt++] = len; 29 int n = len - 1; 30 while (n != -1) 31 { 32 if (Next[n] != -1 && str[ Next[n] ] == str[ len - 1]) 33 ans[cnt++] = Next[n] + 1; // 位置 + 1 34 n = Next[n]; // 不断往前找 35 } 36 for (int i = cnt - 1; i > 0; i--) 37 printf("%d ", ans[i]); 38 printf("%d ", ans[0]); 39 } 40 return 0; 41 }