最长公共子串问题

解题思路

本题要求 $n$ 个字符串的最长公共子串。

先考虑一个简化的问题，对于 $2$ 个字符串，怎么求最长公共子串，我们可以先将字符串 $A$ 建成后缀自动机。然后我们就需要枚举字符串 $B$ 的所有子串，和后缀自动机进行匹配

暴力枚举所有子串就是枚举起点，从每个起点往后走，边走边在后缀自动机中查，直到不能再往后走为止，此时我们就找到了当前起点的一个极大的子串，以此类推枚举完所有起点，这样我们就能将所有子串全部枚举到。从所有子串中取一个最大的能在自动机中查到的子串，就是答案。

暴力肯定会超时，因此需要考虑如何去优化枚举，假设我们从起点 $a$ 开始走，走到 $b$ 为止，此时如果继续走到 $b+1$，则字符串 $a \sim b+1$ 就不在后缀自动机里面出现了，按照暴力此时应该将起点 $a$ 后移一位，再从起点开始枚举子串。此时考虑一下后缀自动机的一些性质，我们在后缀自动机中走到 $b$，不能再向后走了，我们知道 $b$ 这个状态中包含了一串连续的后缀，从 $b$ 不能继续往后走，就意味着 $b$ 这个状态中的所有连续后缀的末尾都不能再加上 $B$ 的后续字符，则如果我们将 $a$ 在 $b$ 这个状态的连续后缀中移动的话，最终得到的字符串都一定只能走到 $b$。

而只有当 $a$ 从当前状态走入新的状态后，此时新的状态中的所有后缀才有可能在 $b$ 之后继续往下走。因此这就启发我们只用每个状态的最长串来更新答案，然后就将起点移动到对应的下一个状态，再用最长串来更新，以此类推。每次移动到下一个状态可以直接用后缀自动机中的 $Link$ 边来移动。

由于沿着 $Link$ 边走每次至少能让 $a$ 后移一位，而每次后移之后，往后最多走到底，也就是字符串 $B$ 的长度，因此若 $B$ 的长度为 $m$，则总移动次数最多只有 $2m$ 次。就是线性的枚举。

这里我们只需要对于每个状态维护一个 $now_p$，表示状态 $p$ 中所有子串在 $B$ 中出现过的最长子串的长度。最终整个的最长公共子串的长度就是所有状态的 $now_i$ 取一个最大值。

此时我们就处理好了两个字符串的最长公共子串。对于多个字符串时，我们可以先按照上述处理，然后对于第 $3$ 个字符串，我们仍旧可以对于第 $1$ 个字符串求一个 $now’_p$，第 $4$ 个字符串也可以对第 $1$ 个字符串求一个 $now’\’_p$，依次类推。那么对于 $now_p$ 和 $now’_p$，我们应该取哪一个呢，我们知道一个状态中的子串一定是连续的后缀，因此如果 $now_p < now’_p$，则 $now_p$ 就一定是 $now’_p$ 的一个子串。按照这个原理，我们要取的就是较小值。所以我们每个状态的 $now_p$ 应该维护一个每个字符串的最长串的最小值，然后再从所有状态的 $now_p$ 中取一个最大值。

注意，这里还有一个特殊情况，就是当某两个串有一个公共后缀，例如 $cba$ 和 $dba$，此时 $ba$ 这个公共子串我们是应该考虑的，但是我们很有可能枚举到 $cba$ 就停止了，并没枚举到后缀，因此我们求完 $now$ 之后，我们还需要将后缀的信息传递出来，而对于所有后缀我们是可以通过原串沿着 $Link$ 边反向访问到的，因此每次求完 $now$，我们都需要通过 $Link$ 边将信息传递过去。这里可以用邻接表建一个 $Link$ 边的反向图，然后沿着反向边递归一遍即可，这里由于我们可能访问不到一些后缀，因此我们可以直接在初始化的时候就将每个状态的答案设置成字符串的最大长度。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20010;

int n;
char str[N];
struct Node
{
    int len, fa;
    int ch[26];
}node[N]; //存储后缀自动机中的所有状态
int tot = 1, last = 1;
//now[i] 表示状态 i 中的最长公共子串的长度
//res[i] 表示状态 i 中的每个字符串的 now[i] 的最小值
int res[N], now[N];
int h[N], e[N], ne[N], idx; //邻接表存储 Link 边的反向边

void extend(int c) //将字符 c 加入后缀数组
{
    int p = last, np = last = ++tot;
    node[np].len = node[p].len + 1;
    for(; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if(!p) node[np].fa = 1;
    else
    {
        int q = node[p].ch[c];
        if(node[q].len == node[p].len + 1) node[np].fa = q;
        else
        {
            int nq = ++tot;
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq; 
            for(; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
}

void add(int a, int b) //添加边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) //递归更新 now 信息
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        now[u] = max(now[u], now[j]); //更新信息
    }
}

int main()
{
    scanf("%d", &n);
    scanf("%s", str);
    for(int i = 0; str[i]; i++) extend(str[i] - 'a'); //将第 1 个字符串的每个字符依次加入后缀自动机
    for(int i = 1; i <= tot; i++) res[i] = node[i].len; //初始化答案
    memset(h, -1, sizeof h); //初始化邻接表
    for(int i = 2; i <= tot; i++) add(node[i].fa, i); //添加 Link 边的反向边

    for(int i = 0; i < n - 1; i++) //用剩下 n - 1 个字符串依次和第 1 个字符串进行匹配
    {
        scanf("%s", str);
        memset(now, 0, sizeof now); //清空 now
        int p = 1, t = 0; //p 表示当前状态，t 表示当前匹配的子串长度
        for(int j = 0; str[j]; j++)
        {
            int c = str[j] - 'a';
            //不是空字符且当前状态不能往下走时，走到下一个状态
            while(p > 1 && !node[p].ch[c]) p = node[p].fa, t = node[p].len;
            if(node[p].ch[c]) p = node[p].ch[c], t++; //如果能往下走，更新
            now[p] = max(now[p], t); //更新当前状态的 now
        }
        dfs(1); //每次更新答案之前将信息传递一下
        for(int j = 1; j <= tot; j++) res[j] = min(res[j], now[j]); //记录每个状态的 now 的最小值
    }

    int ans = 0; //记录答案
    for(int i = 1; i <= tot; i++) ans = max(ans, res[i]); //从所有状态的最小值中取最大值
    printf("%d\n", ans);

    return 0;
}