题意：给你一个字符串s，输出该字符串的所有的前后缀长度
思路：利用next数组的性质，我们知道next[i]是指子串长为i的最大公共前后缀 所以 next[next[i]] 意味着 在最大公共前后缀 的子串里再去寻找最大公共前后缀子串
这样找的原因是
比如给出一个例子： a b a b c a b a b a b a b c a b a b next: -1 0 0 1 2 0 1 2 3 4 3 4 3 4 5 6 7 8 9 所以第一次找到a b a b c a b a b ） a b a b c a b a b 而所找到的最大子串的长度的前缀的尾部 等于 其后缀的尾部a b | a b） c a b a b ） a b a b c a b a b 而再次寻找前缀子串的最大公共前后缀时 其后缀 为 之前后缀的尾部的子串 所以一直递归下去就会发现 每次回溯匹配的时后缀尾部的子串切子串一直在减小 当子串减小到0则意味着结束，也就是len 被递归到0完整代码：
//求前后缀可能性 //用nex数组求出最大的前后缀之后其子的前后缀则必在其之中 #include <iostream> #include <cstdio> #include <cstring> const int maxn = 1e6+5; const int amaxn = 1e3+10; int nex[maxn] ; int len,cnt; int ans[amaxn]; char s[maxn]; void getnext(){ int i,j; i = 0,j=-1; nex[i] =j; while(i<len){ if(j==-1||s[i]==s[j]){ nex[++i] = ++j; }else j = nex[j]; } } void print(){ cnt = 0; ans[cnt] = len; while(len>0){ ans[++cnt] = nex[len]; len = nex[len]; } for(int i= cnt-1;i>0;i--){ printf("%d ",ans[i]); } printf("%d\n",ans[0]); } int main(){ while(~scanf("%s",&s)){ len = strlen(s); getnext(); print(); } }
转载于:https://www.cnblogs.com/Tianwell/p/11212231.html
