锰锌刚学OI,WA0pts求调
查看原帖
锰锌刚学OI,WA0pts求调
520056
luoyx楼主2023/8/12 14:42
#include <bits/stdc++.h>
using namespace std;
int n;
const int N=2e6+5;
char s[N];
struct Trie{
	int cnt=1,ch[N][26],c[N],fa[N];
	void insert(char s[]){
		int p=1;
		for(int i=1;s[i];i++){
			int a=s[i]-'a';
			if(!ch[p][a]) ch[p][a]=++cnt,fa[cnt]=p,c[cnt]=a;
			p=ch[p][a];
		}
	}
}trie;

struct SAM{
	int tot=1,pos[N],fa[N],ch[N][26],len[N];
	int insert(int a,int lst){
		int p=lst,np=lst=++tot;
		len[np]=len[p]+1;
		for(;p&&!ch[p][a];p=fa[p]) ch[p][a]=np;
		if(!p) fa[np]=1;
		else{
			int q=ch[p][a];
			if(len[q]-1==len[p]){
				fa[np]=q;
			}
			else{
				int nq=++tot;
				len[nq]=len[p]+1;
				for(int i=0;i<26;i++) ch[nq][i]=ch[q][i];
				for(;p&&ch[p][a]==q;p=fa[p]) ch[p][a]=nq;
				fa[q]=nq,fa[np]=nq,fa[nq]=p;
			}
		}
		return np;
	}
	void bfs(){
		queue<int> q;
		for(int i=0;i<26;i++){
			if(trie.ch[1][i]){
				q.push(trie.ch[1][i]);
			}
		}
		pos[1]=1;
		while(!q.empty()){
			int u=q.front();
			q.pop();
			pos[u]=insert(trie.c[u],pos[trie.fa[u]]);
			for(int i=0;i<26;i++){
				if(trie.ch[u][i]) q.push(trie.ch[u][i]);
			}
		}
	}
	void solve(){
		long long ans=0;
		for(int i=2;i<=tot;i++){
			ans+=len[i]-len[fa[i]];
		}
		cout<<ans<<endl<<tot<<endl;
	}
}sam;


int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%s",s+1);
		trie.insert(s);
	}
	sam.bfs();
	sam.solve();
}
2023/8/12 14:42
加载中...