在 O(n.logn) 中至少出现两次的最长子串

Question

问题：

给定一个包含 N 个字符的字符串 S(N <= 200 000)，找出至少出现两次（子串可以重叠）的最长子串的长度。

我的解决方案：

这是我试过的方法：

int main()
{
    std::string s;
    std::cin >> s;
    int max = 0;
    typedef std::string::const_iterator sit;
    sit end = s.end();
    for(sit it1 = s.begin(); it1 != end; ++it1)
        for(sit it2 = it1 + 1; it2 != end; ++it2)
            max = std::max(max, std::mismatch(it1, it1 + (end - it2), it2).first - it1);
    std::cout << max;
}

问题：

但是，上述解决方案将在 O(n^3) 中获得 TLE，因为它运行s。有什么方法可以改进它，使其可以在 O(n.logn) 中运行?

Answer 1

find the length of the longest substring that appears at least twice (the substrings can overlap)

这个问题也俗称Longest repeated substring problem。可以用后缀树在线性时间内求解。

解决这个问题：

给给定的字符串 S) 添加一个特殊字符 '$',
从 S 构建后缀树；
S的最长重复子串由后缀树中最深的内部节点表示，其中深度用从根开始遍历的字符数来衡量。

时间复杂度：

后缀树需要O(nlog(k)))时间，其中k是字母表的大小（如果k被认为是常数，则渐近行为是线性的）
树遍历（查找最长重复子串）可以在 O(n) 时间内完成

Answer 2

后缀树对于这个问题来说有点矫枉过正。其实二分查找就够了，实现起来也容易很多。

想法

思路很简单：如果存在重复的长度为N的子串（N > 1），则一定也存在长度为N - 1的子串。因此，如果我们让f(x)表示这样一个函数returns 如果存在长度为 x 的重复子串，则为真，f(x) 将是一个单调函数，允许二进制搜索解决方案。

实施

对最长重复子串的长度进行二进制搜索，并应用 sliding windows 来检查给定的长度是否可能。使用字符串哈希检查重复项。复杂度：N log N

在 O(n.logn) 中至少出现两次的最长子串

Longest substring that appears at least twice in O(n.logn)

c++

string

algorithm

substring

longest-substring

想法

实施