洛谷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;
}