我需要在字符串中找到最长的非重叠重复子串。我有可用字符串的后缀树和后缀数组。
当允许重叠时，答案是微不足道的(后缀树中最深的父节点)。
例如 String = "acaca"
如果允许重叠，答案是“aca”，但当不允许重叠时，答案是“ac”或“ca”。
我只需要算法或高级想法。
P.S.:我试过了，但我在网上找不到明确的答案。
最佳答案
生成后缀数组并在 O(nlogn) 中排序。ps:有更有效的算法，如 DC3 和 Ukkonen 算法。 示例:
字符串:ababc
后缀数组:
子串的起始索引 |子串
0 - ababc
2 - 美国广播公司
1 - babc
3 - 公元前
4-c
比较每两个连续的子字符串并得到具有以下约束的公共(public)前缀:
假设 i1 是子字符串“ababc”的索引:0
假设 i2 是子字符串“abc”的索引:2
公共(public)前缀为"ab"，公共(public)前缀长度为len
abs(i1-i2) >len//避免重叠
用解遍历后缀数组，得到“ababc”的结果，即“ab”；
整个解决方案将运行 O(nlogn)
但是，会有一种特殊情况:“aaaaa”，本方案无法彻底解决。
欢迎讨论，提出O(nlogn)但不是O(n^2)的解决方案
关于algorithm - 使用后缀树/数组的最长非重叠重复子串(仅算法)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12658494/