我们有一个字符串.
ABAEABABEABE
现在我们必须检查是否存在一个子字符串,接下来是另一个子字符串,它与第一个子字符串完全相同.
在这个例子中:ABAEAB ABE ABE
ABE之后是ABE,它是两个相同的子串.
在这个例子中:
AAB
它只是A,因为A后跟另一个A.
在这个例子中:
ABCDEFGHIJKLMNO
没有这样的子串,所以答案是NO.
我只设法找到一个运行在O(n ^ 2)的算法.这是哈希及其前缀.然后,对于每个字母,我们简单地展开并检查以该字母结尾的所有单词.有n个字母.我们需要扩展它n次.所以它是O(n ^ 2).我相信应该有一个针对这个问题的O(n log n)算法.
有没有人有更好的主意？