求调
查看原帖
求调
572133
潘德理2010楼主2023/12/23 16:40
#include<bits/stdc++.h>
using namespace std;
int n,m;
int tr[1000010][26],fa[1000010],cnt[1000010],c,ans;
char s[1000010];
queue<int> q;
void ins(){
	int u=0;
	for(int i=1;i<=m;i++){
		if(tr[u][s[i]-'a']==0){
			tr[u][s[i]-'a']=++c;
		}
		u=tr[u][s[i]-'a'];
	}
	cnt[u]++;
}
void build(){
	for(int i=0;i<26;i++){
		if(tr[0][i]) q.push(tr[0][i]);
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(tr[u][i]){
				fa[tr[u][i]]=tr[fa[u]][i];
				q.push(tr[u][i]);
			}
			else tr[u][i]=tr[fa[u]][i];
		}
	}
}
void que(){
	int u=0;
	for(int i=1;i<=m;i++){
		u=tr[u][s[i]-'a'];
		for(int j=u;j&&cnt[j]!=-1;j=fa[j]){
			ans+=cnt[j];
			cnt[j]=-1;
		}
	}
}
int main(){
//	freopen("P3808_2.in","r",stdin);
	scanf("%d",&n);
	s[0]='*';
	for(int i=1;i<=n;i++){
		scanf("%s",s+1);
		m=strlen(s)-1;
		ins();
	}
	scanf("%s",s+1);
	m=strlen(s)-1;
	que();
	printf("%d",ans);
}
2023/12/23 16:40
加载中...