题目链接：SPOJ 220

你是 Byteland 的国王，你的特工刚刚截获了 $n$ 条敌方的加密信息 $s_i$。你请来的密码学家声称他只能解密文本中最重要的部分，这个文字片段在所有信息中至少出现 $2​$ 次且不相交。你需要求出这个文字片段的最长长度。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 10$，$1 \le n \le 10$，$2 \le \lvert s_i \rvert \le 10 ^ 4$。

Solution

这个题目和「POJ 1743」Musical Theme（题解）非常相似，只不过把 $1$ 个字符串转化为 $n$ 个字符串。于是我们只需要记录每个字符串中的 $sa(i)$ 的最大值和最小值。如果 $n$ 个字符串都满足最大值减最小值不小于二分的长度，那么合法。

唯一需要注意的是：对字符串的标记撤销操作不能暴力进行，否则复杂度是错的。

时间复杂度：$\mathcal O(n \log n)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

const int N = 1e5 + 5;
const int INF = 0x7f7f7f7f;

int n, m, a[N], bl[N], mx[N], mn[N];
bool flg[N];

template <int S>
struct SuffixArray {
    static const int N = S << 1;
    int n, m, a[N], sa[N], rk[N], bin[N], tmp[N], height[N];
    void clear() {
        memset(a, 0, sizeof(a));
        memset(sa, 0, sizeof(sa));
        memset(rk, 0, sizeof(rk));
        memset(height, 0, sizeof(height));
    }
    void radixSort() {
        for (int i = 1; i <= m; i++) bin[i] = 0;
        for (int i = 1; i <= n; i++) bin[rk[i]]++;
        for (int i = 1; i <= m; i++) bin[i] += bin[i - 1];
        for (int i = n; i >= 1; i--) sa[bin[rk[tmp[i]]]--] = tmp[i];
    }
    template <class Tp>
    void build(Tp *_a, int _n, int _m) {
        n = _n, m = _m;
        std::copy(_a + 1, _a + n + 1, a + 1);
        for (int i = 1; i <= n; i++) rk[i] = a[i], tmp[i] = i;
        radixSort();
        for (int l = 1, p = 0; p < n; l <<= 1, m = p) {
            p = 0;
            for (int i = n - l + 1; i <= n; i++) tmp[++p] = i;
            for (int i = 1; i <= n; i++) if (sa[i] > l) tmp[++p] = sa[i] - l;
            radixSort();
            std::swap(rk, tmp);
            p = rk[sa[1]] = 1;
            for (int i = 2; i <= n; i++) {
                rk[sa[i]] = (tmp[sa[i - 1]] == tmp[sa[i]] && tmp[sa[i - 1] + l] == tmp[sa[i] + l]) ? p : ++p;
            }
        }
        for (int i = 1, k = 0; i <= n; i++) {
            k -= (k > 0);
            int j = sa[rk[i] - 1];
            for (; a[i + k] == a[j + k]; k++);
            height[rk[i]] = k;
        }
    }
};

SuffixArray<N> A;

bool check(int x) {
    memset(mx, 0, sizeof(mx));
    memset(mn, 0x7f, sizeof(mn));
    memset(flg, false, sizeof(flg));
    int cnt = 0;
    std::vector<int> v;
    for (int i = 1; i <= n; i++) {
        int t = bl[A.sa[i]];
        if (A.height[i] >= x) {
            mx[t] = std::max(mx[t], A.sa[i]);
            mn[t] = std::min(mn[t], A.sa[i]);
            v.emplace_back(t);
            if (t && mx[t] - mn[t] >= x) {
                if ((cnt += (!flg[t])) == m) return true;
                flg[t] = true;
            }
        } else {
            cnt = 0;
            for (int t: v) mx[t] = 0, mn[t] = INF, flg[t] = false;
            mx[t] = std::max(mx[t], A.sa[i]);
            mn[t] = std::min(mn[t], A.sa[i]);
            v.clear(), v.emplace_back(t);
        }
    }
    return false;
}
int main() {
    int T;
    for (scanf("%d", &T); T--; ) {
        scanf("%d", &m);
        n = 0;
        for (int i = 1; i <= m; i++) {
            static char s[N];
            scanf("%s", s + 1);
            int len = strlen(s + 1);
            for (int j = 1; j <= len; j++) a[++n] = s[j], bl[n] = i;
            a[++n] = i + 256, bl[n] = 0;
        }
        A.clear();
        A.build(a, n, m + 256);
        int l = 0, r = 5000, ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            check(mid) ? l = (ans = mid) + 1 : r = mid - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}