【算法】KMP
【題解】KMP中n-next[n]得到最小循環節的性質。
考慮一個循環串（最後一個循環節可能殘缺），它最長的【字尾=字首】一定是以第二個循環節為起始位置的字尾。
正着考慮的話假設字尾T以x+1開始，S為字首那：
1.S(1~x)=T(1~x)即S(x+1~2x)
2.S(x+1~2x)=T(x+1~2x)即S(2x+1~3x)。
這樣疊加到最後就是循環串了。
注意：
1.當fail[n]=0的時候，循環節預設為自身要判否。
2.n/(n-fail[n])表示循環次數，不能整除說明循環節殘缺。
#include<cstdio>
const int maxn=1000010;
char s[maxn];
int n,p[maxn];
int main()
{
scanf("%d%s",&n,s+1);
int j=0;p[1]=0;
for(int i=2;i<=n;i++)
{
while(j>0&&s[j+1]!=s[i])j=p[j];
if(s[j+1]==s[i])j++;
p[i]=j;
}
printf("%d",n-p[n]);
return 0;
} View Code
轉載于:https://www.cnblogs.com/onioncyc/p/6622433.html