KMP.zip_字符模板

#include<cstdio> #include<cstring> using namespace std; void next(const char P[],int next[]) { int q,k;//q:模版字符串下标；k:最大前后缀长度 int m = strlen(P);//模版字符串长度 next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0 for (q = 1,k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的next值 { while(k > 0 && P[q] != P[k])//递归的求出P[0]···P[q]的最大的相同的前后缀长度k k = next[k-1]; //不理解没关系看下面的分析，这个while循环是整段代码的精髓所在，确实不好理解 if (P[q] == P[k])//如果相等，那么最大相同前后缀长度加1 { k++; } next[q] = k; } } int ne[1000005]; int main() { char s[1000005]; while(scanf("%s",&s)&&(s[0]!='.')) { next(s,ne); int len=strlen(s); if(len%(len-ne[len-1])==0) { printf("%d\n",len/(len-ne[len-1])); } else printf("1\n"); } return 0; } /*题意：给一个字符串S长度不超过10^6，求最大的n使得S由n个相同的字符串a连接而成，如："ababab"则由n=3个"ab"连接而成，"aaaa"由n=4个"a"连接而成，"abcd"则由n=1个"abcd"连接而成。 定理：假设S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len]整除，最短循环子串为S[len - next[len]] 例子证明： 设S=q1q2q3q4q5q6q7q8，并设next[8] = 6，此时str = S[len - next[len]] = q1q2，由字符串特征向量next的定义可知，q1q2q3q4q5q6 = q3q4q5q6q7q8，即有q1q2＝q3q4，q3q4＝q5q6，q5q6＝q7q8，即q1q2为循环子串，且易知为最短循环子串。由以上过程可知，若len可以被len - next[len]整除，则S存在循环子串，否则不存在。 解法：利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，则最大循环次数n为len/(len - next[len])，否则为1 */