[AC自动机模板题] HDU 2222 Keywords Search

模板题

考前复习

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#define cl(x) memset(x,0,sizeof(x))
using namespace std;

inline char nc()
{
	static char buf[100000],*p1=buf,*p2=buf;
	if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
	return *p1++;
}

inline void read(int &x)
{
	char c=nc(),b=1;
	for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
	for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline int read(char *s)
{
	char c=nc(); int len=0;
	for (;!(c>='a' && c<='z');c=nc());
	for (;c>='a' && c<='z';s[++len]=c,c=nc()); s[++len]=0; return len-1;
}

const int M=260200;

int ncnt,root,ch[M][26];
int val[M],f[M],last[M];

inline void Insert(char *str,int len){
	int p=root;
	for (int i=1;i<=len;i++)
	{
		if (!ch[p][str[i]-'a']) ch[p][str[i]-'a']=++ncnt;
		p=ch[p][str[i]-'a'];
	}
	val[p]++;
}

queue<int> Q;

inline void GetFail(){
	f[0]=0; int u,v,t;
	for (int i=0;i<26;i++)
		if (ch[0][i])
			last[ch[0][i]]=f[ch[0][i]]=0,Q.push(ch[0][i]);
	while (!Q.empty()){
		u=Q.front(); Q.pop();
		for (int i=0;i<26;i++)
		{
			v=ch[u][i];
			if (!v) { ch[u][i]=ch[f[u]][i]; continue; }
			Q.push(v);
//			t=f[u];
//			while (t && !ch[t][i]) t=f[t];
//			f[v]=ch[t][i]; 
			f[v]=ch[f[u]][i];
			last[v]=val[f[v]]?f[v]:last[f[v]];
		}
	}
}

int ans=0;

inline void print(int p){
	if (!p) return;
	ans+=val[p]; val[p]=0;
	print(last[p]);
}

inline void Find(char *str,int len){
	int p=0;
	for (int i=1;i<=len;i++){
		p=ch[p][str[i]-'a'];
		print(p);
	}
}

int n,Len;
char S[1000005];

inline void clear(){
	ncnt=0; cl(ch); cl(f); cl(last); cl(val);
}

int main()
{
	int T;
	freopen("t.in","r",stdin);
	freopen("t.out","w",stdout);
	read(T);
	while (T--)
	{
		read(n);
		for (int i=1;i<=n;i++)
		{
			Len=read(S);
			Insert(S,Len);
		}
		Len=read(S);
		GetFail();
		ans=0;
		Find(S,Len);
		printf("%d\n",ans);
		clear();
	}
	return 0;
}