洛谷P9089 「SvR-2」Work 题解

题意：

给定 \(n\) 个由小写字母组成的字符串，定义第 \(i\) 个字符串的价值为其有意义的子串的数量（如果有多个本质相同的子串也统计多次），第 \(i\) 个字符串的一个子串有意义，当且仅当这个子串能被分成若干个串，其中每个串都是这 \(n\) 个字符串中任意一个字符串的任意一个后缀。

这里有一个 \(n=4\) 的例子：
int
printf
scanf
ntnt
对于 printf 这个字符串而言，intf 是有意义的，因为可以表示成 int 和 f ，分别是 int 和 scanf 的后缀，而 rint 则不是。

对于 ntnt 这个字符串而言，ntnt 也是有意义的，因为可以表示成 nt 和 nt，它们都是 int 同一个后缀，或者可以表示成 ntnt，是 ntnt 的一个后缀。

现在，小 Z 想知道这 \(n\) 个字符串价值之和。

输入格式：

第一行一个整数 \(n\)。

之后 \(n\) 行，每行一个字符串。

输出格式：

一行一个整数，表示价值之和。

数据范围：

令 \(s_i\) 表示第 \(i\) 个字符串长度，\(1\le n \le 5\times10^5\)，\(n\le \sum\limits \lvert s_i \rvert \le 10^6\)。

先把所有串翻转一下，此时一个串 \(S\) 有意义当且仅当它可以被分解成若干个已知串的前缀。

不妨定义一个串的匹配是它的后缀与某个 \(s_i\) 的前缀相同，则这个后缀就是它的一个匹配。

则一个串 \(S\) 有意义的充要条件是 \(S\) 的每一个前缀都有匹配。

我们可以通过每次删掉一个串的最短匹配来验证这个串有意义，因为我们一定能找到这样的匹配。

令 \(g_u\) 表示 \(u\) 节点代表的字符串在 Trie 中出现过的最短后缀。

当 \(\operatorname{fail}(u)\) 存在时 \(g_u \gets g_{\operatorname{fail}(u)}\) ，否则 \(g_u\) 的最短后缀就是它自己。

令 \(f_i\) 表示（当前串）以 \(i\) 结尾的后缀有多少个是合法的，易得 \(f_i = f_{i - g_u} + 1\) 。

另外，我们可以用一种更为简洁的构建方式来构建 AC 自动机：（详见参考文献[1]）

考虑 \(x\) 是由 Trie 中的父亲 \(f\) 通过 \(c\) 转移边得到的。

检索 \(y=\mathrm{fail}(f)\) ，若 \(y\) 存在字符 \(c\) 的转移边，则令 \(x\) 指向 \(\mathrm{tr}(y,c)\) 。否则, 令 \(y \leftarrow \mathrm{fail}(y)\) 即不断跳 fail 检查是否有 \(c\) 出边。若到了根节点依然没有 \(c\) 出边，则令 \(\mathrm{fail}(x)\) 指向初始节点。

对于每个串（在 Trie 中自顶向下），尝试寻找 fail 的 \(y\) 在最终 fail 树中的深度变化，每次向下走一个儿子 \(y\) 深度最多 \(+1\) ，每次暴力跳 fail 深度都会 \(-1\) ，均摊下来总的时间复杂度就是 \(\mathcal{O}\left(\sum|s_i|\right)\).

那么有同学会说了，你这是在干什么呢？

众所周知，如果我们建字典图，时间复杂度就是 \(\mathcal{O}\left(|\Sigma|\cdot \sum|s_i|\right)\) ，只不过这个 \(|\Sigma|\) 通常是 \(26\) 而已。

而这个构建方式，就是 OI wiki 上提到的：不连 trie 图，并且在构建 fail 指针的时候避免遍历到空儿子。

然后我久违的又去请教 Roundgod 了，他说一般没人会卡这个，并且主流写法都是建字典图。

时间复杂度 \(\mathcal{O}(\sum |s_i|)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
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)(1e6 + 15))

int n,f[N],g[N],dep[N]; string s[N];
int pos = 1,tot,fa[N],head[N],fail[N],tr[N][26];
struct Edge { int u,v,c,next; } e[N];
void addEdge(int u,int v,int c)
{
    tr[u][c] = v; fa[v] = u; dep[v] = dep[u] + 1;
    e[++pos] = {u,v,c,head[u]}; head[u] = pos;
}
void insert(string s)
{
    int u = 0, l = s.size();
    for(int i = 0; i < l; i++)
    {
        int c = s[i] - 'a';
        if(!tr[u][c]) addEdge(u, ++tot, c);
        u = tr[u][c];
    }
}
void build()
{
    queue<pii> q;
    for(int i = 0; i < 26; i++) if(tr[0][i]) q.push({tr[0][i], i});
    while(!q.empty())
    {
        int u,c,x; tie(u,c) = q.front(); q.pop();
        for(x = fail[fa[u]]; x && !tr[x][c]; x = fail[x]);
        if(x != fa[u]) fail[u] = tr[x][c];
        g[u] = fail[u] ? g[fail[u]] : dep[u];
        for(int i = head[u]; i; i = e[i].next) q.push({e[i].v, e[i].c});
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        reverse(s[i].begin(), s[i].end()); insert(s[i]);
    }
    build(); int res = 0;
    for(int o = 1; o <= n; o++)
    {
        int m = s[o].size(), u = 0; f[0] = 0;
        for(int i = 1; i <= m; i++)
        {
            u = tr[u][s[o][i - 1] - 'a'];
            f[i] = f[i - g[u]] + 1; res += f[i];
        }
    }
    cout << res << '\n';
    return 0;
}