string - 最大子串搜索

Question

给定一个字符串 S，由小写拉丁字母组成。我想为每个位置 S[i] 最大长度 L[i] 找到一个位置 i' < i that s[i'..i'+L[i]-1] = s[i.. i+L[i]-1]。例如：s = ababaab，L= {0,0,3,2,1,2,1}。我想在 < O(|S|^2) 的时间内完成。我猜这个问题是用后缀数组解决的，但是如何解决呢？

Answer 1

你应该看看 ZBlock 算法，虽然这个算法解决了一个稍微不同的问题（其中 i' 总是等于 0），它运行在 O(|S|) 中。您应该可以在方便时对其进行修改。

动态编程将使用修改后的子字符串匹配版本在 O(|S|^2) 中解决这个问题，但我猜你不是在寻找这样的解决方案。

Answer 2

您正在寻找的东西被称为“最长的先前因子”，并且确实有 Crochemore 和 Ilie 的一篇论文，其中包含两个后缀数组算法来计算这一点。好消息是两者都是线性时间。第二种算法使用 Lcp 表，在我看来要容易一些。