在KMP算法中 next[l] 记录的就是字符串最长的相同的前缀与后缀，也就是说在题目字符串中有一段字符串是重复出现的，那么减去重复出现的字符串以后，剩下的就是这个字符串最小的循环节。
比较字符串的 next 数组
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| s1 | c | a | b | c | a | b | c | a | b | c | a |
| next | -1 | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| s2 | b | c | d | a | b | c | d | a | b | c | d |
| next | -1 | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
s1 的循环节：abc 或 bca、cab
s2 的循环节：abcd 或 bcda、cdab、dabc
结果符合预期
实现代码
#include<bits/stdc++.h>
using namespace std;
int next[1000010];
string s;
void get_next(){
int j=-1, i=0;
next[0]=-1;
while(i<s.size()){
if(j==-1||s[j]==s[i]){
j++;
i++;
next[i] = j;
}
else
j = next[j];
}
return ;
}
int main(){
int n;
scanf("%d", &n);
cin>>s;
get_next();
/* printf(" %c ", s[0]);
for(int i=1; i<=s.size(); i++)
printf("%c ", s[i]);
printf("\n");
for(int i=0; i<=s.size(); i++)
printf("%d ", next[i]);
printf("\n");*/
printf("%d", n-next[n]);
return 0;
}