Elastic Search

题目链接：Elastic Search

---

我们不难发现，对于一个串，就是一直找子串，然后求一下找的最大次数。
我们可以发现，我们对于一个有子串关系的暴力建图，然后求最长路即可。
这里复杂度肯定不行，我们可以注意到，每次假设可以到 abba，也可以到ab，那么一定是前者。所以相当于就是AC自动机上面每次跳fail的一个dp。
这里为了保证复杂度，每个节点只访问一次，所以需要记忆化。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+10;
int n,res,id[N];	string str[N]; unordered_map<string,int> mp;
int c[N][26],ed[N],fail[N],idx,pos[N],dp[N];
inline void insert(string str,int idd){
	int p=0;
	for(int i=0;i<str.size();i++){
		int k=str[i]-'a';
		if(!c[p][k]) c[p][k]=++idx;
		p=c[p][k];
	}
	ed[p]++,pos[idd]=p;
}
inline void build(){
	queue<int> q;
	for(int i=0;i<26;i++) if(c[0][i]) fail[c[0][i]]=0,q.push(c[0][i]);
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=0;i<26;i++)
			if(c[u][i]) fail[c[u][i]]=c[fail[u]][i],q.push(c[u][i]);
			else c[u][i]=c[fail[u]][i];
	}
}
int dfs(int p){
    if(dp[p]||!p) return dp[p];
    return dp[p]=dfs(fail[p]);
}
inline void calc(string str,int idd){
	int p=0,mx=0;
	for(int i=0;i<str.size();i++){
		p=c[p][str[i]-'a'];
		mx=max(mx,dfs(p));
	}
	dp[pos[idd]]=mx+ed[pos[idd]];
	res=max(res,dp[pos[idd]]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>str[i],id[i]=i,insert(str[i],i); build();
	sort(id+1,id+1+n,[](int a,int b){return str[a].size()<str[b].size();});
	for(int i=1;i<=n;i++) if(!mp.count(str[id[i]])) calc(str[id[i]],id[i]),mp[str[id[i]]]=1;
	cout<<res;
	return 0;
}