POJ 2406 Power Strings——kmp求最短循环子串

POJ 2406 Power Strings——kmp求最短循环子串

题意：给你一个字符串，如果这个字符串可以由某个子串重复多次构成，那么输出最大重复次数。

如abcd 输出 1；

aaaa 输出 4；

ababab 输出 3；

定理：假设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

#include #include #include #include #include using namespace std;string s;int len, Next[1000010];void makeNext() { int i = 0, j = 0; Next[i] = j; for (i = 1; i < len; i++) { while (j && s[i] != s[j]) j = Next[j - 1]; if (s[i] == s[j]) j++; Next[i] = j; }}int main() { while (cin >> s && s[0] != '.') { len = s.size(); makeNext(); int L = len - Next[len - 1]; printf("%d\n", (len % L) ? 1 : len / L); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。