Rei*_*uma 9 string algorithm hash substring
我们有一个字符串.
ABAEABABEABE
现在我们必须检查是否存在一个子字符串,接下来是另一个子字符串,它与第一个子字符串完全相同.
在这个例子中:ABAEAB ABE ABE
ABE之后是ABE,它是两个相同的子串.
在这个例子中:
AAB
它只是A,因为A后跟另一个A.
在这个例子中:
ABCDEFGHIJKLMNO
没有这样的子串,所以答案是NO.
我只设法找到一个运行在O(n ^ 2)的算法.这是哈希及其前缀.然后,对于每个字母,我们简单地展开并检查以该字母结尾的所有单词.有n个字母.我们需要扩展它n次.所以它是O(n ^ 2).我相信应该有一个针对这个问题的O(n log n)算法.
有没有人有更好的主意？
这个问题可以通过“分而治之”Main-Lorentz 算法来解决：
Michael Main，Richard J. Lorentz。用于查找字符串中所有重复项的 O (n log n) 算法 [1982]
编辑：俄语的算法描述和 C++ 实现（可以用 Chrome 浏览器翻译）
还存在线性时间算法（不知道实际实现）
| 归档时间： |
|
| 查看次数： |
412 次 |
| 最近记录： |