AcWing 2811. 最长公共子串 题解

题目分析

本题要求给定(n)个仅由小写字母构成的字符串，求出这些字符串的最长公共子串的长度。数据范围为(2\leq n\leq11)，每个字符串长度不超过(10000)。

解题思路

本题使用后缀自动机（Suffix Automaton）来求解。后缀自动机是一种可以在线性时间内处理字符串所有后缀信息的数据结构。通过构建第一个字符串的后缀自动机，然后依次将其他字符串与后缀自动机进行匹配，从而找出最长公共子串的长度。
1. 后缀自动机的构建：extend函数用于在线性时间内构建后缀自动机。对于输入的字符，根据当前状态和字符，更新后缀自动机的节点信息，包括节点的长度、父亲节点以及转移边。
2. 图的构建与辅助函数：add函数用于构建后缀自动机节点之间的树状结构（从后缀自动机的父亲指针构建）。dfs函数用于对构建好的树进行深度优先搜索，更新每个节点能达到的最长匹配长度。
3. 字符串匹配与结果计算：在主函数中，先构建第一个字符串的后缀自动机，并初始化一些数组。然后依次读入其余字符串，与后缀自动机进行匹配，更新当前字符串在后缀自动机各节点上的最长匹配长度。通过深度优先搜索更新整个后缀自动机各节点的最长匹配长度，并取所有字符串在各节点匹配长度的最小值。最后遍历所有节点，找出其中的最大值，即为最长公共子串的长度。

代码逐段分析

1. 头文件和全局变量定义

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20010;

int n;
int tot = 1, last = 1;
char str[N];
struct Node
{
    int len, fa;
    int ch[26];
}node[N];
int ans[N], now[N];
int h[N], e[N], ne[N], idx;

• 引入必要的头文件，包括输入输出、字符串操作和算法相关的头文件。
• 定义常量(N)表示后缀自动机节点的最大数量。
• 变量(n)表示字符串的数量。
• tot表示后缀自动机节点的总数，初始为(1)；last表示当前后缀自动机的最后一个节点，初始也为(1)。
• str[N]用于存储输入的字符串。
• 定义结构体Node，包含节点的长度len、父亲节点fa以及字符转移数组ch[26]（表示从该节点出发，对于(26)个小写字母的转移情况）。
• ans[N]用于存储在所有字符串匹配过程中，每个后缀自动机节点能匹配到的最长公共子串长度；now[N]用于临时存储当前字符串在后缀自动机各节点上的最长匹配长度。

• h[N]、e[N]和ne[N]用于构建后缀自动机节点之间的树状结构（邻接表相关数组），idx用于记录边的编号。

• 后缀自动机扩展函数

void extend(int 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;
        }
    }
}

• 该函数用于向后缀自动机中添加一个字符c。
• 首先创建一个新节点np，其长度为前一个最后节点p的长度加(1)，并更新last为np。
• 然后从last节点开始，沿着父亲指针向上遍历，若当前节点没有字符c的转移边，则添加一条指向np的转移边。
• 如果遍历到根节点（p == 0），则将np的父亲节点设为根节点（编号为(1)）。

• 否则，找到第一个有字符c转移边的节点q：

  • 如果q的长度等于p的长度加(1)，则将np的父亲节点设为q。
  • 否则，创建一个新节点nq，复制q的信息，并将q和np的父亲节点都设为nq，同时更新之前指向q的转移边，使其指向nq。

• 添加边函数

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

• 该函数用于在后缀自动机节点构成的树状结构中添加一条从节点a到节点b的边，采用邻接表的方式存储。

• 深度优先搜索函数

void dfs(int u)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        dfs(e[i]);
        now[u] = max(now[u], now[e[i]]);
    }
}

• 该函数对后缀自动机节点构成的树状结构进行深度优先搜索。
• 从节点u出发，遍历其所有子节点，递归调用dfs函数。

• 更新节点u的now[u]值为其自身和所有子节点now值中的最大值，即取能达到的最长匹配长度。

• 主函数

int main()
{
    scanf("%d", &n);
    scanf("%s", str);
    for (int i = 0; str[i]; i ++ ) extend(str[i] - 'a');
    for (int i = 1; i <= tot; i ++ ) ans[i] = node[i].len;
    memset(h, -1, sizeof h);
    for (int i = 2; i <= tot; i ++ ) add(node[i].fa, i);

    for (int i = 0; i < n - 1; i ++ )
    {
        scanf("%s", str);
        memset(now, 0, sizeof now);
        int p = 1, t = 0;
        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);
        }
        dfs(1);
        for (int j = 1; j <= tot; j ++ ) ans[j] = min(ans[j], now[j]);
    }

    int res = 0;
    for (int i = 1; i <= tot; i ++ ) res = max(res, ans[i]);
    printf("%d\n", res);

    return 0;
}

• 读入字符串的数量n和第一个字符串str。
• 通过extend函数构建第一个字符串的后缀自动机。
• 将后缀自动机各节点的初始最长匹配长度设为节点自身的长度，存储在ans数组中。
• 初始化邻接表头指针数组h，并根据后缀自动机的父亲指针构建树状结构（添加边）。
• 对于剩下的(n - 1)个字符串：
  • 读入字符串，初始化now数组。
  • 从后缀自动机的根节点开始，依次匹配字符串的每个字符：如果当前节点没有对应的转移边，则沿着父亲指针向上回溯，并更新匹配长度t；如果有转移边，则沿着转移边移动，并增加匹配长度。同时更新now数组中对应节点的最长匹配长度。
  • 调用dfs函数更新整个后缀自动机各节点的最长匹配长度。
  • 取ans数组和当前字符串的now数组对应位置的最小值，更新ans数组。
• 遍历ans数组，找出其中的最大值，即为所有字符串的最长公共子串的长度，最后输出结果。

时间复杂度分析

• 构建后缀自动机的时间复杂度为(O(L))，其中(L)是第一个字符串的长度。
• 对于每个剩余字符串，与后缀自动机匹配的时间复杂度为(O(L_i))，(L_i)是该字符串的长度，总共(n - 1)个字符串，所以这部分时间复杂度为(O(\sum_{i = 2}^{n}L_i))。
• 深度优先搜索的时间复杂度为(O(tot))，其中tot是后缀自动机节点的总数，由于tot与字符串总长度相关，可认为与(O(\sum_{i = 1}^{n}L_i))同阶。
• 总体时间复杂度为(O(\sum_{i = 1}^{n}L_i))，其中(L_i)是第(i)个字符串的长度。

空间复杂度分析

主要空间消耗在于后缀自动机的节点数组、邻接表相关数组以及辅助数组等，空间复杂度为(O(\sum_{i = 1}^{n}L_i)) 。