AC自动机,不知道哪里T了希望大佬能看一下
查看原帖
AC自动机,不知道哪里T了希望大佬能看一下
37938
打工战士铃羽楼主2020/5/29 13:55
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

const int L=1e6+10;

int ans,sum[L],fail[L],n,trans[L][27],cnt;
char A[L],B[L];

void insert (char *s) {
	int now=0;
	for(int i=0;i<strlen(s);i++) {
		if(!trans[now][s[i]-'a']) { trans[now][s[i]-'a']=++cnt; now=cnt; }
		else now=trans[now][s[i]-'a'];
	}
	sum[now]++;
}

void MakeFail () {
	queue<int> q;
	for(int i=0;i<26;i++) 
		if(trans[0][i]) q.push(trans[0][i]);
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int i=0;i<26;i++) {
			if(trans[u][i]) fail[trans[u][i]]=trans[fail[u]][i],q.push(trans[u][i]);
			else trans[u][i]=trans[fail[u]][i];
		}
	}
}

void Query() {
	int u=0;
	for(int i=0;i<strlen(B);i++) {
		u=trans[u][B[i]-'a'];
		for(int j=u;j>0 && sum[j]!=-1;j=fail[j]) {
			ans+=sum[j]; sum[j]=-1;
		}
	}
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		scanf("%s",A); 
		insert(A);
	}
	scanf("%s",B);
	MakeFail();
	Query();
	cout<<ans;
}
2020/5/29 13:55
加载中...