KMP之Power Strings

NEFU 2131 字符串乘方

模拟过程：
这道题十分巧妙地运用了next数组的性质；
$s[0...next[i]]=s[i-next[i]+1...i]$s[0...next[i]]=s[i−next[i]+1...i]

若s字符串存在重复，则如图所示

next数组的构建：

1. $next[i]$next[i]数组就是描述：最长当前$1-i$1−i长度的字符串的最长前缀和后缀的长度。
2. 如果存在重复单元，则$len-next[len]$len−next[len]就是最短的循环串。
3. 当$len\mod(len-next[len])=0$lenmod(len−next[len])=0的话，就会存在循环节。则$len/(len-next[len])$len/(len−next[len])就是答案。

举例：

字符串:    a b c a b c a b c
next数组:  0 0 0 1 2 3 4 5 6

字符串:    a b c d a b c e
next数组:  0 0 0 0 1 2 3 0

字符串:    a a a a a a a b
next数组:  0 1 2 3 4 5 6 0

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const int maxn = 1e6 + 5;
char s[maxn];
int Next[maxn];
int main()
{
    while (~scanf("%s", s))
    {
        if (s[0] == '.')
            break;
        int len = strlen(s);
        memset(Next, 0, sizeof(Next));
        int i = 0, j = -1;
        Next[0] = -1;   //s[i]代表后缀，s[j]代表前缀
        while (i < len) //next定义为最长的前缀==后缀
        {
            if (j == -1 || s[i] == s[j])
            {
                i++;
                j++;
                Next[i] = j;
            }
            else
                j = Next[j];
        }                                           
        if (len % (len - Next[len]) == 0)            //如果第i-1位为结尾的循环必定有 i % (i - Next[i]) == 0
            printf("%d\n", len / (len - Next[len])); //0～i-1共有i个字符，i / (i - Next[i])就是循环次数。
        else
            printf("1\n");
    }
    return 0;
}