在 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。有什么方法可以改进它以便它可以在 O(n.logn) 中运行？

Answer 1

后缀树对于这个问题来说有点过分了。事实上，二分查找就足够了，而且实现起来也容易得多。

主意

想法很简单：如果存在长度为 N (N > 1) 的重复子串，则也一定存在长度为 N - 1 的重复子串。因此，如果我们让 f(x) 表示一个函数，如果存在则返回 true长度为 x 的重复子串，f(x) 将是一个单调函数，它允许二分搜索解决方案。

执行

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