1
A
回答
1
这是一个简单的O(n)算法,依靠后缀树构造。
将原始字符串s和补码串s'加载到相同的后缀树(O(n)time)中。然后通过为每个节点x设置两个标志f(x)和f'(x),在f(x)(或f'(x))包含s(后缀) S')。现在简单地遍历树,寻找具有两个标志设置的最深节点,并且发现s中最长的字符串,其补码也出现在s中。后处理也仅花费O(n)时间,因此总运行时间为O(n)。
0
下面的算法是最坏的情况下O(n * n)
和平均情况只是有点超线性。当有很多很长的常见子字符串时,它遇到了最坏的情况。
考虑可以通过在字符串中的任意位置开始形成的子字符串集。一旦只有一个可能的匹配,就构建这些子字符串的一个trie,该字符串以指向原始字符串中某个位置的指针结尾。你必须为n个子字符串中的每一个工作这个trie,但是你只需要通过该字符串与其他任何其他字符串中最长的公共子字符串来跟踪它。
一旦你建立了这个数据结构,通过查找树的递归遍历,寻找一个子串与它的补码进行配对。由于你只需要配对相反的子字符串,而不是子字符串与字符串中其他所有的位置,因此trie的结构应该使配对非常有效。
如果某些字符在共同点不常见时很常见,那么您可以通过延迟建立trie来提高性能。
相关问题
- 1. 后缀树:最长的重复子字符串实现
- 2. 后缀树和最长的重复子字符串问题
- 3. 最长的重复子字符串后缀树dfs
- 4. 找到最长的字符串前缀
- 5. 查找重复字符的最长的子字符串中的
- 6. 算法找到最长后缀的字符串和所述字符串的前缀之间的长度
- 7. 所有后缀的最长前缀字符串长度
- 8. 二进制搜索树到字符串
- 9. 查找字符串数组中最长的字符串
- 10. 最长的子字符串
- 11. 查找字符串中最长重复子字符串所需的Java函数?
- 12. 在字符串python中查找最长的唯一子字符串
- 13. 查找最小长度子字符串包含所有的字符串
- 14. 十六进制字符串到二进制字符串
- 15. Ruby:十六进制字符串到二进制字符串
- 16. 二进制字符串到十六进制字符串java
- 17. SQL最长前缀字符串
- 18. Json_encode二进制字符串
- 19. 字符串到二进制[]
- 20. 字符串为二进制
- 21. 按字母顺序查找最长的子字符串
- 22. 查找其他字符串的前缀字符串
- 23. 查找字符串的字符串w /最低频字符
- 24. 如何查找Swift字符串中子字符串的最后一次出现?
- 25. C++查找子字符串中最后一次发生的字符串
- 26. 在Python中以字符串的数字顺序查找最长的字符串
- 27. 查找字符串C#字符的最发生,返回最长的复现字符的字符串
- 28. 字符串的后缀
- 29. 计算字符串中最长的回文子字符串
- 30. 查找字符串的二维数组中的字符串数
你能澄清吗?你想要一个补码字符串吗? – Patrick
确切(我想找到最长的一个)。 – user550413