我从用户那里获取一个输入，它是一个带有特定子字符串的字符串，该子字符串在整个字符串中重复出现。我需要输出子字符串或其长度 AKA period。
说
S1 = AAAA // substring is A
S2 = ABAB // Substring is AB
S3 = ABCAB // Substring is ABC
S4 = EFIEFI // Substring is EFI
我可以从单个字符开始，检查它是否与下一个字符相同，如果不相同，我可以先用两个字符，然后用三个，依此类推。这将是一个 O(N^2) 算法。我想知道是否有更优雅的解决方案。
最佳答案
您可以通过归纳计算字符串每个前缀的周期，在线性时间和常量附加空间内完成此操作。我不记得细节(有几件事需要做对)，但你可以在 Section 13.6 of "Text algorithms" by Crochemore and Rytter under function Per(x) 中找到它们。 .
关于string - 如何找到字符串的周期，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21169045/