algorithm - 如何使用后缀树在线性时间内找到这样的字符串？

Question

给定一个长度为 n 的字符串 s，找到在 s 中向前和向后都出现的最长字符串 t。 例如，s = yabcxqcbaz，然后返回 t = abc 或 t = cba

我正在考虑使用广义后缀树，但我认为这会花费 O(n^2) 时间。

i = 0 # Initialize the position on the S
j = 0 # Initialize the position on the Sr
n = len(S) # n is the length of the string
maxLengthPos = (0, 0) # Record the maximum length of such substring found so far and its position

# Iterate through every 
for i in range(n):
    for j in range(n):
        maxL, pos = maxLengthPos
        l = LCE(i, j) # The longest common extension which take O(1) time
        if l > maxL:
            maxLength = (l, i)

我能否在 O(n) 时间内实现它？

Answer 1

您正在寻找 longest common substring s 及其反面。这确实可以在线性时间内使用 s 和 reverse(s) 的广义后缀数组或后缀树来解决。

有一种概念上更简单的方法，使用 suffix automaton的虽然。后缀自动机是精确匹配字符串后缀的有限自动机，可以在线性时间内构建。您可以在 C++ 中找到一个实现 in my Github repository .现在您只需将第二个字符串(在本例中为 reverse(s))输入自动机并记录最长的匹配，它对应于两个字符串的 LCS。