如何检测字符串中的回文循环长度？

Question

假设一个字符串是这样的"abaabaabaabaaba"，这里的回文循环是3，因为你可以在每第3个位置找到字符串aba，你可以通过连接任意数量的[=15=来增加回文]s 到字符串。

我认为使用 Manacher 的算法可以有效地检测到这一点，但是如何呢？

Answer 1

在S+S中搜索字符串S即可轻松找到。您找到的第一个索引是您想要的循环编号（可能是整个字符串）。在 python 中会是这样的：

In [1]: s = "abaabaabaabaaba"

In [2]: print (s+s).index(s, 1)
3

1 是为了忽略索引 0，那将是一个微不足道的匹配。