题意：给一个字符串S长度不超过10^6，求最大的n使得S由n个相同的字符串a连接而成，如："ababab"则由n=3个"ab"连接而成，"aaaa"由n=4个"a"连接而成，"abcd"则由n=1个"abcd"连接而成。
利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，则最大循环次数n为len/(len - next[len])，否则为1。
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int N = 1000002; int next[N]; char S[N], T[N]; int slen, tlen; void kmp_pre(char x[],int m,int Next[]) { int i,j; j=Next[0]=-1; i=0; while(i<m) { while(-1!=j&&x[i]!=x[j]) j=Next[j]; Next[++i]=++j; } } int main() { while(~scanf("%s",S)) { int n=strlen(S); if (n==1&&S[0]==‘.‘) { break; } kmp_pre(S,n,next); if (n%(n-next[n])==0) { printf("%d\n",n/(n-next[n])); } else { puts("1"); } } return 0; }
PKU 2406 Power Strings（KMP最长循环不重叠字串）
原文：http://www.cnblogs.com/s1124yy/p/5685765.html