【AC自动机 DP】The 16th Heilongjiang Provincial Collegiate Programming Contest E. Elastic Search

题链

题目解析

给定 $n$ 个字符串，如果串 $a$ 是串 $b$ 的子串，那么 $b$ 向 $a$ 连接一条有向边，求最长路径；

对所有字符串构建 $AC$ 自动机，定义：
  $fa[u]$ 为字典树上 $u$ 节点的父亲；
  $fail[u]$ 为失配指针；
  $num[u]$ 表示以 $u$ 节点为结尾的有多少字符串；

对字符串的每一个前缀进行 $dp$，也就是对字典树上每一个节点 $dp$；
对于一个字符串，走向下一个字符串要么就是去头，要么去尾；
于是转移公式 $dp[u]=max(dp[fa[u]],dp[fail[u]])+num[u]$；

由于求 $fail$ 的时候会破坏原有字典树结构，$dp$ 又是在原有字典树结构上 $dp$ 的，所以重构一遍这个字典树或者新建一个就可以 $dp$ 了；

代码实现

#include <bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
	#define gg(x) cout << #x << ": " << x << "\n";
	#define LL long long
	#define ULL unsigned long long
	#define Pair pair<LL ,LL >
	#define ls rt<<1
	#define rs rt<<1|1
	#define PI acos(-1.0)
	#define eps 1e-8
	#define MAXN 9e18
	#define fi first
	#define se second
	#define ll long long
	#define MS 500009
	#define mod 1000000007

int n,m,k;
char s[MS];
int dic[MS][26], fail[MS], num[MS], tot;
int dicc[MS][26], fa[MS];
queue<int > Q;
int dp[MS], ans;

void insert(){
	int u = 0;
	for(int i=1;s[i];i++){
		int t = s[i]-'a';
		if(!dic[u][t]) ++tot, dic[u][t] = dicc[u][t] = tot, fa[tot] = u;
		u = dic[u][t];
	}
	num[u]++;
}

void init_fail(){
	for(int i=0;i<26;i++) if(dic[0][i]) Q.push(dic[0][i]);
	while(!Q.empty()){
		int u = Q.front(); Q.pop();
		for(int i=0;i<26;i++){
			if(dic[u][i]) fail[dic[u][i]] = dic[fail[u]][i], Q.push(dic[u][i]);
			else dic[u][i] = dic[fail[u]][i];
		}
	}
}

void bfs(){
	for(int i=0;i<26;i++) if(dicc[0][i]) Q.push(dicc[0][i]);
	while(!Q.empty()){
		int u = Q.front(); Q.pop();
		dp[u] = max(dp[fa[u]],dp[fail[u]]) + num[u];
		ans = max(ans,dp[u]);
		for(int i=0;i<26;i++) if(dicc[u][i]) Q.push(dicc[u][i]);
	}
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> s+1, insert();
	init_fail();
	bfs();
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	int ce = 1;
//	cin >> ce;
	while(ce--) {
		solve();
	}

	return 0;
}