Radio Transmission

https://loj.ac/problem/10045

题目描述

　　给出一个字符串，求最短循环节长度。

思路

　　KMP求最短循环节，跑一遍KMP即可。具体关于这个最短循环节的结论见Power Strings

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
char s[MAXN];
int pre[MAXN];
int main() 
{
    int n;
    scanf("%d",&n);
    scanf(" %s",s+1);
    int j=0;pre[1]=0;
    for(int i=1;i<n;i++)
    {
        while(j>0&&s[i+1]!=s[j+1])j=pre[j];
        if(s[i+1]==s[j+1])j++;
        pre[i+1]=j;
    }
    printf("%d",n-pre[n]);
    return 0;
}