AcWing 2766. 后缀自动机 题解

题目分析

本题给定一个只包含小写字母的字符串(S)，需要找出(S)中出现次数不为(1)的子串，计算其出现次数与子串长度的乘积(value)，并返回所有这些(value)中的最大值。

解题思路

本题主要通过构建后缀自动机（SAM）来解决。后缀自动机可以高效地处理字符串的子串相关问题，通过构建SAM并对其进行遍历，统计每个状态所代表子串的出现次数，进而计算出满足条件的最大(value)值。
1. 构建后缀自动机：利用extend函数逐个字符扩展后缀自动机，该函数根据后缀自动机的性质进行状态的添加和连接。
2. 建立状态之间的父子关系：通过add函数构建状态之间的树形关系，方便后续遍历。
3. 深度优先遍历：使用dfs函数对后缀自动机进行深度优先遍历，统计每个状态所代表子串的出现次数，并计算最大的(value)值。

代码逐段分析

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

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

using namespace std;

typedef long long LL;

const int N = 2000010;

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

• 引入必要的头文件，包括输入输出、字符串操作和算法相关的头文件。
• 定义LL为long long的别名。
• 定义常量(N)表示后缀自动机状态的最大数量。
• tot表示当前状态的总数，初始为(1)；last表示上一个添加的状态，初始为(1)。
• 定义结构体Node，每个节点包含子串长度len、父节点编号fa以及字符转移数组ch[26]，用于表示从该状态通过不同字符转移到的下一个状态。
• str[N]用于存储输入的字符串。
• f[N]用于记录每个状态所代表子串的出现次数。
• ans用于存储最终的答案，即最大的(value)值。

• h[N]、e[N]、ne[N]和idx用于构建邻接表，存储状态之间的父子关系。

• 扩展后缀自动机函数

void extend(int c)
{
    int p = last, np = last = ++ tot;
    f[tot] = 1;
    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)，并初始化其出现次数为(1)。
• 然后从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]);
        f[u] += f[e[i]];
    }
    if (f[u] > 1) ans = max(ans, f[u] * node[u].len);
}

• 该函数用于对后缀自动机进行深度优先遍历。
• 从节点u出发，遍历其所有子节点e[i]，递归调用dfs函数，并将子节点的出现次数累加到当前节点u的出现次数上。

• 如果当前节点u所代表子串的出现次数大于(1)，则计算其(value)值（出现次数乘以子串长度），并更新ans为较大值。

• 主函数

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

    return 0;
}

• 读入输入的字符串str。
• 逐个字符扩展后缀自动机。
• 初始化邻接表的头指针数组h为(-1)。
• 构建状态之间的父子关系，将每个状态与其父状态连接起来。
• 从根状态（编号为(1)）开始进行深度优先遍历。
• 输出最大的(value)值ans。

时间复杂度分析

• 构建后缀自动机的过程中，每个字符的扩展操作时间复杂度为(O(1))，总共(n)个字符，所以构建后缀自动机的时间复杂度为(O(n))，其中(n)是字符串的长度。
• 建立状态之间的父子关系以及深度优先遍历的时间复杂度也为(O(n))。
• 总体时间复杂度为(O(n))。

空间复杂度分析

主要空间消耗在于存储后缀自动机的状态数组、邻接表相关数组以及辅助变量等，空间复杂度为(O(n))。