如何以O(n·logn)复杂度求解至少出现两次的最长子串长度

给定长度为N（N ≤ 200000）的字符串S，求至少出现两次的最长子串的长度，子串允许重叠。原暴力实现的时间复杂度为O(n³)，无法处理大规模数据，需要优化到O(n·logn)级别。

思路 #

• 二分枚举可能的子串长度L，每次判断是否存在至少两个长度为L的相同子串：
  • 若存在，说明可以尝试更长的子串，调整二分左边界
  • 若不存在，说明需要缩短长度，调整二分右边界
• 判断环节使用滚动哈希预处理所有长度为L的子串的哈希值，将哈希值排序后检查是否有重复值即可，单次判断时间复杂度为O(n)
• 整体二分次数为O(logn)，总时间复杂度为O(n·logn)

代码实现 #

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;
const int BASE = 131;
vector<ull> hash_val, power;

void init(const string& s) {
    int n = s.size();
    hash_val.resize(n + 1, 0);
    power.resize(n + 1, 1);
    for (int i = 0; i < n; i++) {
        hash_val[i + 1] = hash_val[i] * BASE + s[i];
        power[i + 1] = power[i] * BASE;
    }
}

ull get_hash(int l, int r) { // 区间左闭右开，子串长度为r-l
    return hash_val[r] - hash_val[l] * power[r - l];
}

bool check(int L, int n) {
    if (L == 0) return true;
    vector<ull> hashes;
    for (int i = 0; i + L <= n; i++) {
        hashes.push_back(get_hash(i, i + L));
    }
    sort(hashes.begin(), hashes.end());
    for (int i = 1; i < hashes.size(); i++) {
        if (hashes[i] == hashes[i - 1]) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    init(s);
    int n = s.size();
    int left = 0, right = n - 1, ans = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid, n)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

注：如果担心ull自然溢出的哈希碰撞问题，可以使用双模数哈希进一步降低碰撞概率，不会改变时间复杂度级别。

思路 #

• 后缀数组是将字符串的所有后缀按字典序排序后得到的下标数组
• 两个后缀的最长公共前缀长度，就是这两个后缀对应公共子串的最大长度。而排序后，最长的公共前缀一定出现在相邻的两个后缀中，因此只需要计算相邻后缀的LCP，取最大值即可得到答案
• 用倍增法构建后缀数组的时间复杂度为O(n·logn)，计算LCP数组的时间复杂度为O(n)，总复杂度满足要求

代码实现 #

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> sa, rk, height;

void build_sa(const string& s) {
    int n = s.size(), m = max(256, n);
    sa.resize(n), rk.resize(n), height.resize(n);
    vector<int> x(n), y(n), cnt(max(n, m));
    for (int i = 0; i < n; i++) cnt[x[i] = s[i]]++;
    for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--cnt[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int p = 0;
        for (int i = n - k; i < n; i++) y[p++] = i;
        for (int i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;
        fill(cnt.begin(), cnt.begin() + m, 0);
        for (int i = 0; i < n; i++) cnt[x[y[i]]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1; x[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? p - 1 : p++;
        }
        if (p >= n) break;
        m = p;
    }
}

void build_height(const string& s) {
    int n = s.size(), k = 0;
    for (int i = 0; i < n; i++) rk[sa[i]] = i;
    for (int i = 0; i < n; i++) {
        if (rk[i] == 0) continue;
        if (k) k--;
        int j = sa[rk[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        height[rk[i]] = k;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    build_sa(s);
    build_height(s);
    int ans = 0;
    for (int i = 1; i < s.size(); i++) {
        ans = max(ans, height[i]);
    }
    cout << ans << endl;
    return 0;
}

内容的提问来源于stack exchange，提问作者unglinh279