题目链接:http://poj.org/problem?id=2752
题意是给了一个字符串,求出前i位的前缀刚好是后i位的后缀,输出这些位置,比如abcab当i为2的时候前缀为ab后缀也为ab
思路就是根据Next数组的性质,通过当前符合的公共前后缀的长度,去找到前缀的位置,然后依次往前找直到为0为止,可能这么说不太好理解,建议根据Next数组的值然后去画一下第一个样例就好了,最后因为字符串本身就是一个前后缀,所以最后要加上一个字符串的本身长度。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define maxn 1000005
using namespace std;
char s[maxn];
int pre[maxn], Next[maxn];
int cnt;
void init(){
int j = 0, k = -1;
memset(Next, -1, sizeof(Next));
int len = strlen(s);
while(j < len){
if(k == -1 || s[j] == s[k]){
k ++;
j ++;
Next[j] = k;
}
else k = Next[k];
}
}
int main()
{
while(~scanf("%s", s)){
init();
int len = strlen(s);
cnt = 0;
int xx = Next[len];
while(xx){
pre[cnt ++] = xx;
xx = Next[xx];
}
for(int i=cnt-1;i>=0;i--){
printf("%d ", pre[i]);
}
printf("%d\n", len);
}
return 0;
}