如何查找字符串的句点

Question

我从用户那里得到一个输入,它带有一个带有某个子串的字符串,它在字符串中重复出现.我需要输出子串或其长度AKA周期.

说

S1 = AAAA // substring is A
S2 = ABAB // Substring is AB
S3 = ABCAB // Substring is ABC
S4 = EFIEFI // Substring is EFI

我可以从一个单一字符开始并检查它是否与它的下一个字符是相同的,如果不是,我可以用两个字符然后用三个等来做它.这将是一个O(N ^ 2)算法.我想知道是否有更优雅的解决方案.

Answer 1

您可以通过归纳计算字符串的每个前缀的周期来在线性时间和恒定的额外空间中执行此操作.我不记得细节(有几件事情要做),但你可以在Crochemore和Rytter的第13.6节"文本算法"中function Per(x)找到它们.