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

Question

假设一个字符串是这样的“abaabaabaabaaba”，这里的回文周期是3，因为你可以在每个第3个位置找到字符串aba，并且你可以通过将任意数量的“aba”连接到字符串来增强回文。

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

Answer 1

通过在S+S中搜索字符串S就可以轻松找到它。您找到的第一个索引是您想要的循环编号(可能是整个字符串)。在 python 中，它会是这样的:

In [1]: s = "abaabaabaabaaba"

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

1 用于忽略索引 0，这将是一个简单的匹配。