标签: 字符串 二分查找 后缀数组 滑动窗口 哈希函数 滚动哈希
难度: Hard
给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。
返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。
示例 1：
输入：s = "banana" 输出："ana"
示例 2：
输入：s = "abcd" 输出：""
提示：
2 <= s.length <= 3 * 104s 由小写英文字母组成运行时间: 362 ms
内存: 21.0 MB
def inducedSort(s: List[int], sa1: List[int], t: List[int], m=26):
n = len(s)
cnt = [0] * m
for i in range(n):
cnt[s[i]] += 1
for i in range(1, m):
cnt[i] += cnt[i - 1]
start, end = [0] + cnt[:-1], cnt[:]
sa = [-1] * n + [n]
for x in reversed(sa1[1:]):
cnt[s[x]] -= 1
sa[cnt[s[x]]] = x
for i in range(-1, n):
if sa[i] > 0:
c = sa[i] - 1
if not t[c]:
sa[start[s[c]]] = c
start[s[c]] += 1
for i in range(n - 1, -1, -1):
if sa[i] > 0:
c = sa[i] - 1
if t[c]:
end[s[c]] -= 1
sa[end[s[c]]] = c
return sa[:-1]
def SA_IS(s: List[int], m=26):
n = len(s)
t = [False] * (n + 1)
for i in reversed(range(n - 1)):
t[i] = t[i + 1] if s[i] == s[i + 1] else (s[i] < s[i + 1])
critical = list()
for i in range(1, n):
if t[i] and not t[i - 1]:
critical.append(i)
nc = len(critical)
index = [-1] * n + [n]
for i, x in enumerate(critical):
index[x] = i
sa0 = inducedSort(s, [n] + critical, t, m)
s1 = [0] * (nc + 1)
critical.append(n)
last, p, repeat = "", 0, False
for x in sa0:
if index[x] >= 0:
c = s[x : critical[index[x] + 1]]
if c != last:
p += 1
last = c
else:
repeat = True
s1[index[x]] = p
if repeat:
sa1 = [critical[x] for x in SA_IS(s1, p + 1)]
else:
sa1 = [n] + [x for x in sa0 if index[x] >= 0]
return inducedSort(s, sa1, t, m)
def suffixArray(s: str) -> (List[int], List[int], List[int]):
n, k = len(s), 0
sa = SA_IS([ord(x) - 97 for x in s])
rk = [0] * n
for i in range(n):
rk[sa[i]] = i
height = [0] * n
s += '#'
for i in range(n):
if rk[i]:
if k > 0:
k -= 1
while s[i + k] == s[sa[rk[i] - 1] + k]:
k += 1
height[rk[i]] = k
return rk, sa, height
class Solution:
def longestDupSubstring(self, s: str) -> str:
rk, sa, height = suffixArray(s)
mh = max(height)
start = sa[height.index(mh)]
return s[start : start + mh]
这个题解使用了后缀数组的思想。主要步骤如下： 1. 通过 SA-IS 算法构建后缀数组 sa 和 rk 数组。sa[i] 表示将所有后缀排序后第 i 小的后缀的起始位置，rk[i] 表示后缀 s[i:] 在 sa 中的排名。 2. 通过 sa 和 rk 计算 height 数组。height[i] 表示 sa[i] 和 sa[i-1] 这两个后缀的最长公共前缀（LCP）的长度。 3. 在 height 数组中找到最大值 mh，则最长重复子串长度为 mh，起始位置为 sa[height.index(mh)]。
时间复杂度: O(n)
空间复杂度: O(n)
def inducedSort(s: List[int], sa1: List[int], t: List[int], m=26):
n = len(s)
cnt = [0] * m
for i in range(n):
cnt[s[i]] += 1
for i in range(1, m):
cnt[i] += cnt[i - 1]
start, end = [0] + cnt[:-1], cnt[:]
sa = [-1] * n + [n]
for x in reversed(sa1[1:]):
cnt[s[x]] -= 1
sa[cnt[s[x]]] = x
for i in range(-1, n):
if sa[i] > 0:
c = sa[i] - 1
if not t[c]:
sa[start[s[c]]] = c
start[s[c]] += 1
for i in range(n - 1, -1, -1):
if sa[i] > 0:
c = sa[i] - 1
if t[c]:
end[s[c]] -= 1
sa[end[s[c]]] = c
return sa[:-1]
def SA_IS(s: List[int], m=26):
n = len(s)
t = [False] * (n + 1)
for i in reversed(range(n - 1)):
t[i] = t[i + 1] if s[i] == s[i + 1] else (s[i] < s[i + 1])
critical = list()
for i in range(1, n):
if t[i] and not t[i - 1]:
critical.append(i)
nc = len(critical)
index = [-1] * n + [n]
for i, x in enumerate(critical):
index[x] = i
sa0 = inducedSort(s, [n] + critical, t, m)
s1 = [0] * (nc + 1)
critical.append(n)
last, p, repeat = "", 0, False
for x in sa0:
if index[x] >= 0:
c = s[x : critical[index[x] + 1]]
if c != last:
p += 1
last = c
else:
repeat = True
s1[index[x]] = p
if repeat:
sa1 = [critical[x] for x in SA_IS(s1, p + 1)]
else:
sa1 = [n] + [x for x in sa0 if index[x] >= 0]
return inducedSort(s, sa1, t, m)
def suffixArray(s: str) -> (List[int], List[int], List[int]):
n, k = len(s), 0
sa = SA_IS([ord(x) - 97 for x in s]) # 构建后缀数组
rk = [0] * n # 初始化 rk 数组
for i in range(n):
rk[sa[i]] = i # 计算 rk 数组
height = [0] * n # 初始化 height 数组
s += '#' # 在字符串末尾添加一个特殊字符，以避免边界判断
for i in range(n):
if rk[i]: # 从 rk[i] > 0 的后缀开始计算 height
if k > 0:
k -= 1
while s[i + k] == s[sa[rk[i] - 1] + k]: # 计算 sa[rk[i]] 和 sa[rk[i]-1] 的 LCP
k += 1
height[rk[i]] = k
return rk, sa, height
class Solution:
def longestDupSubstring(self, s: str) -> str:
rk, sa, height = suffixArray(s)
mh = max(height) # 找到 height 数组中的最大值
start = sa[height.index(mh)] # 最长重复子串的起始位置
return s[start : start + mh] # 返回最长重复子串
SA-IS算法在构建后缀数组时具有高效和低内存消耗的优点。与后缀树相比，后缀数组更加简洁，占用内存更少，且SA-IS算法的时间复杂度为O(n)，非常适合处理大规模数据。相较于Burrows-Wheeler变换，SA-IS直接构建后缀数组，适用性更广，且在实现上更直接。此外，SA-IS算法适用于多种字符集和复杂度较低，这使得它在实际应用中非常受欢迎。
后缀数组sa包含了字符串的所有后缀的起始位置的排序索引，即sa[i]是第i小的后缀的起始位置。排名数组rk是后缀数组的逆序数组，即rk[i]表示后缀s[i:]在所有后缀中的排序位置。最长公共前缀数组height记录了排序后相邻两个后缀的最长公共前缀长度，具体来说，height[i]是sa[i]和sa[i-1]的最长公共前缀长度。这三个数组互相配合，可以高效地解决字符串的多种问题，如最长重复子串的查找。
在字符串末尾添加一个特殊字符`#`（通常是一个在字符串中未出现过的最小字符）的目的是为了保证计算最长公共前缀时边界的正确性。这个特殊字符确保了字符串的任何后缀都不会与其它后缀完全相同，从而避免了在计算过程中对字符串末尾的越界访问，同时简化了比较逻辑，因为加入特殊字符后，不需要额外的条件判断来停止比较。
变量k用于记录当前比较中已匹配的字符数。在计算最长公共前缀时，k的初始值设为0，表示开始时没有任何匹配。递减k的操作是为了利用已知的信息减少重复比较。具体来说，如果上一次比较已经找到了k个匹配字符，那么下一次比较可以从第k个字符开始，而不是重新从头开始比较。这种技术称为LCP数组的'phi'技巧，可以有效减少比较的总次数，提高算法效率。