如何将KMP算法应用于http://www.spoj.com/problems/PERIOD/等字符串问题？

Question

我已经学习了KMP算法,但未能在字符串问题中实现它.谁能建议我如何使用KMP算法在SPOJ中完成上述问题？链接:http://www.spoj.com/problems/PERIOD/

Answer 1

假设前缀长度i为的前缀函数是p[i].
如果i mod (i - p[i]) == 0那么K = i / (i - p[i])其他K = 1(证据的概念是任何时期是最小时期的倍数,而最小时期是确切的i - p[i]).
因此,您可以使用KMP算法为字符串的所有前缀计算前缀函数,然后使用上面的公式.