50pt求调
查看原帖
50pt求调
375242
ynxynx楼主2022/7/5 10:53

rt

#include<bits/stdc++.h>
using namespace std;
const int N=1000001;
struct AC{
	int fail,num;
	int ch[27];
}tr[N];
queue <int> q;
int n,cnt;
char cha[N];
void inser() {
	int len=strlen(cha),u=0;
	for (int i=0;i<len;i++) {
		int t=cha[i]-'a';
		if (!tr[i].ch[t]) tr[i].ch[t]=++cnt;
		u=tr[i].ch[t];
	}
	tr[u].num++;
}
void bfs(){
	for (int i=0;i<26;i++) {
		if (tr[0].ch[i]) {
			tr[tr[0].ch[i]].fail=0;
			q.push(tr[0].ch[i]);
		}
	}
	while (!q.empty()) {
		int now=q.front();
		q.pop();
		for (int i=0;i<26;i++) {
			if (!tr[now].ch[i]) {
				tr[now].ch[i]=tr[tr[now].fail].ch[i];
			}
			else {
				tr[tr[now].ch[i]].fail=tr[tr[now].fail].ch[i];
				q.push(tr[now].ch[i]);
			}
		}
	}
}
char s[N];
int ACZDJ(){
	int len=strlen(s);
	int now=0,ans=0;
	for(int i=0;i<len;i++)	{
		int t=s[i]-'a';
		now=tr[now].ch[t];
		int v=now;
		while(v && tr[v].num!=-1){
			ans+=tr[v].num;
			tr[v].num=-1;
			v=tr[v].fail;
		}
	}
	return ans;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%s",cha),inser();
	bfs();
	scanf("%s",s);
	printf("%d\n",ACZDJ());
	return 0;
}
2022/7/5 10:53
加载中...