自动搬运

查看原文

来自洛谷，原作者为

	do_while_true 水

搬运于2025-08-24 22:45:15，当前版本为作者最后更新于2023-02-23 16:05:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

来个时间复杂度真的线性的做法。

前面的部分和题解区那个 AC 自动机做法相同。先都 reverse 一下，找下充分条件，一个串 $S$ 合法当且仅当它的所有前缀都存在一个后缀在 Trie 里面出现过。必要性构造就是每次删掉当前这个前缀的最短的后缀。

然后考虑根据这个必要性的构造划分等价类来 dp。

首先 $g_u$ 表示 $u$ 节点代表字符串在 Trie 中出现过的最短后缀，当 $fail_u$ 存在时 $g_u\gets g_{fail[u]}$，否则 $g_u$ 没有真后缀，那么这个最短后缀就是它自己。

然后 $f_i$ 表示当前这个串以 $s_i$ 为结尾的后缀有多少个是合法的，首先 $s[:i]$ 是合法的，然后删掉它看它前面能接上几个，就是 $f_{i-g[u]}$，这里 $u$ 是 $s[:i]$ 在 Trie 中代表的节点。

注意到这里并不需要求出 AC 自动机的转移边，仅需要 Trie 边以及 fail 树。所以这样构建：

考虑 $x$ 是由 Trie 中的父亲 $fa$ 通过 $c$ 转移边得到的。那么检索 $y=fail_{fa}$，若 $y$ 存在字符 $c$ 的转移边，则令 $x$ 指向 $tr_{y,c}$；否则，令 $y\gets fail_y$ 即不断跳 fail 检查是否有 $c$ 出边。若到了初始节点（Trie 的根节点）依然没有 $c$ 出边，则令 $fail_x$ 指向初始节点。

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

所以总的时间复杂度是 $\mathcal{O}(\sum |s|)$，并不会乘上一个字符集大小。

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
const int N=1000010;
int n;
int tr[N][26],fa[N],fail[N],dep[N],g[N],tot;
int head[N],ent;
struct Edge{
	int nxt,to,col;
}e[N];
int f[N];
void add(int x,int y,int c){
	tr[x][c]=y;fa[y]=x;dep[y]=dep[x]+1;
	e[++ent]={head[x],y,c};head[x]=ent;
}
void Ins(string &s){
	int u=0,l=s.size();
	for(int i=0;i<l;i++){
		if(!tr[u][s[i]-'a'])add(u,++tot,s[i]-'a');
		u=tr[u][s[i]-'a'];
	}
}
void build(){
	queue<pii>q;
	for(int i=0;i<26;i++)if(tr[0][i])q.push(mp(tr[0][i],i));
	while(!q.empty()){
		int u=q.front().fi,c=q.front().se;q.pop();
		int x=fail[fa[u]];
		while(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].nxt)q.push(mp(e[i].to,e[i].col));
	}
}
string s[N];
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> s[i];
		reverse(s[i].begin(),s[i].end());
		Ins(s[i]);
	}
	build();
	long long ans=0;
	for(int o=1;o<=n;o++){
		int m=s[o].size(),u=0;f[0]=0;
		for(int i=0;i<m;i++){
			u=tr[u][s[o][i]-'a'];
			f[i]=f[i-g[u]]+1;
			ans+=f[i];
		}
	}
	cout << ans << '\n';
	return 0;
}