SP10570 LONGCS - Longest Common Substring 题解

题意：

子串是字符串的连续部分。一个通常用动态规划解决的问题是找到最长公共子串问题，即找到两个字符串的最长子串（或多个最长子串）。你的任务是找到 $K$ 个字符串的最长公共子串的长度。

输入格式：

第一行包含一个整数 $T$，表示测试用例的数量 $(1 \le T \le 20)$ 。

每个测试用例包含一行，包含一个整数 $K(1 \le K \le 10)$

以及接下来的 $K$ 行，每行包含一个字符串（字符串长度 $\le 10^4$），这些字符串只包含字符 a 到 z。

输出格式：

输出 $T$ 行，每行对应一个测试用例，包含所需的序列，每个连续的项之间用一个空格分隔。

保证序列中的所有项都是整数。

这道题的思路和洛谷P3181 [HAOI2016] 找相同字符很相似。

考虑将所有的串用特殊字符拼接成一个串，然后构建后缀数组。

于是问题转化为：找到 $K$ 个后缀（且没有后缀在同一个串中），这 $K$ 个后缀的最长公共前缀的长度的最大值。

直接枚举后缀的位置未免过于那什么了，我们可以给不同串染上颜色，然后枚举后缀的排名

那么问题进一步转化为：找到 $K$ 个位置（颜色互不相同）的 height 值的最小值的最大值。

（~~cxy：最小值的最大值？二分！~~）别急，实际上这题不用二分。

不妨记 $T_i$ 为第 $i$ 个后缀，设 $\operatorname{LCP}(i,j) = \operatorname{lcp}(T_{\texttt{sa[i]}}, T_{\texttt{sa[j]}})$ 为排名 $i$ 和 $j$ 的后缀的最长公共前缀的长度

那么写成式子的话就是下面这个（方便起见，假设 $K=3$ ）

$\begin{aligned} \max_{1 \leq i<j<k \leq n}\left\{ \operatorname{lcp}\left(T_{\texttt{sa[i]}}, T_{\texttt{sa[j]}}, T_{\texttt{sa[k]}}\right) \right\} &=\max_{1 \leq i<j<k \leq n}\left\{ \min\{\operatorname{LCP}(i,j),\,\operatorname{LCP}(j,k) \}\right\} \\[6pt]&= \max_{1 \leq i<j<k \leq n}\left\{ \min_{i+1\le l \le k}\{\texttt{height[l]}\}\right\} \end{aligned}$

那么这相当于求一个有 $K$ 种颜色的区间 $[l,r]$ ，它的 height 最小值的最大值。

可以发现，当 $l$ 固定时最小的 $r$ 单调不增（更大的 $r$ 显然不会更优）

于是这个问题就变成了，双指针维护区间 $[l,r]$ ，求 $[l,r]$ 内最小值。滑动窗口？单调队列！

时间复杂度 $\mathcal{O}(n \log n)$ 或 $\mathcal{O}(n)$ ，取决于建后缀数组 SA 的复杂度。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 55))
#define mem(a) memset(a, 0, sizeof(a))
#define check(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])

char t[N]; deque<int> q;
int s[N], sa[N], rk[N * 2], col[N], tmp[N * 2], height[N], cnt[N];
void sort(const int n, const int m, int w)
{
    memset(cnt, 0, sizeof(int) * (m + 5));
    for(int i = 1; i <= n; i++) tmp[i] = sa[i];
    for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
void getlcp(const int n)
{
    int k = 0;
    for(int i = 1; i <= n; height[rk[i]] = k, i++)
    {
        const int j = sa[rk[i] - 1]; if(k) --k;
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
    }
}
void init(const int n)
{
    const int m = max(n, 666);
    for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
    for(int w = 1; w < n; w *= 2)
    {
        sort(n, m, w); sort(n, m, 0);
        for(int i = 1; i <= n; i++) tmp[i] = rk[i];
        for(int i = 1, p = 0; i <= n; i++)
            if(check(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
    }
}
void work()
{
    int tot, n = 0; cin >> tot; mem(tmp); mem(col); mem(rk); mem(sa);
    for(int i = 1; i <= tot; s[++n] = 233 + i, i++)
    {
        cin >> (t + 1);
        for(int j = 1; t[j]; j++) { s[++n] = t[j], col[n] = i; }
    }
    if(tot == 1) { return cout << strlen(t + 1) << '\n', void(0); }
    s[n--] = 0; init(n); getlcp(n); mem(tmp);
    int sum = 0, res = 0; while(!q.empty()) q.pop_back();
    for(int i = n - tot + 1, r = n - tot + 1; i >= 1; i--)
    {
        if(!tmp[col[sa[i]]]) { ++sum; } ++tmp[col[sa[i]]];
        while(r >= i && sum == tot && tmp[col[sa[r]]] != 1) { --tmp[col[sa[r]]], --r; }
        while(!q.empty() && q.front() > r) q.pop_front();
        if(sum == tot) up(res, height[q.front()]);
        while(!q.empty() && height[q.back()] > height[i]) q.pop_back();
        q.push_back(i);
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) work();
    return 0;
}