Power Strings

https://loj.ac/problem/10035

题目描述

  给出一个字符串，求它的最小循环节。

思路

  之前讲过(Hash)的做法，不过这也是(KMP)的模板题。

  我们有结论：若(n\%(n - p [ n ])==0)，最小循环节长度为(n/(n - p [ n ]))；否则就为它本身。

  我们对着证明考虑两部分，一是可以整除时为什么这是答案，而是为什么不能整除是最小循环节为它本身。

  (①)如果(n)是((n - p [ n ]))的倍数，我们可以把字符串分为若干段长((n - p [ n ]))的字符串。首先我们把每段记为(A、B、C、D)(假设只有四段)，所以(D)段表示的是字符串(S[ p[ n ]，n ])这一段，而由(P)数组的定义我们可知(p[ n ])表示的(n)的最长公共前后缀，即(S[ 1 ...p[ n ] ])前缀和(S[ p[ n ] ...n ])后缀相同，所以我们有(ABC=BCD)(表示字符串依次连接)，由于它们完全相等，所以(A=B，B=C，C=D)，所以可知(A)就是循环节，而很容易由反证法知道不存在更短的循环节，否则和(p)数组定义不符。其数目即为答案。

  (②)我们需要解决为什么不整除时就最小循环节就是它本身。我们运用反证法，假设存在最小循环节长(len(len！=n))，那么(S[ 1，len ]=S[ n-len，n ])，那么(len=n - p[n])，而由假设知，(n)不被(n - p [ n ])整除，但又由循环节定义知(n)被(len)整除，因此矛盾。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int pre[MAXN];
char s[MAXN];
int main() 
{
    while(~scanf(" %s",s+1))
    {
        int n=strlen(s+1);
        if(s[1]=='.')break ;
        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;
        }
        if(n%(n-pre[n])==0)printf("%d
",n/(n-pre[n]));
        else printf("1
");
    }
    return 0;
}