Power Strings POJ - 2406 （KMP求最小循环节）

题目 https://cn.vjudge.net/problem/POJ-2406

题意

用next数组求出整个数组的最大前缀，如果整个串是用循环节组成的，那么 n - next[n] 也就是最小循环节，验证最小循环节会被n整出。

思路

利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，则最大循环次数n为len/(len - next[len])，否则为1。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int nex[1000005];
char s[2000006];void kmpNext(char *p)
{int t = nex[0] = -1;int n =strlen(p);int j = 0;while(j<n){if(t== -1||p[t]==p[j]){j++;t++;nex[j] = t;}elset = nex[t];}
}int main()
{while(scanf("%s",s) != EOF){if(s[0] == '.'){break;}memset(nex,0,sizeof(nex));kmpNext(s);int len = strlen(s);if(len%(len - nex[len]) == 0){printf("%d\n",len/(len-nex[len]));}elseprintf("1\n");}return 0;
}