algorithm - 使用后缀树/数组的最长非重叠重复子串(仅算法)

Question

我需要在字符串中找到最长的非重叠重复子串。我有可用字符串的后缀树和后缀数组。

当允许重叠时，答案是微不足道的(后缀树中最深的父节点)。

例如 String = "acaca"

如果允许重叠，答案是“aca”，但当不允许重叠时，答案是“ac”或“ca”。

我只需要算法或高级想法。

P.S.:我试过了，但我在网上找不到明确的答案。

Answer 1

生成后缀数组并在 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)的解决方案