luoguP3796[模板]AC自动机（加强版）

传送门

ac自动机模板，可能我写的ac自动机是有点问题的，所以跑的有些慢

暴力跳fail统计

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

void read(int &x) {

	char ch; bool ok;

	for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;

	for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;

}

#define rg register

const int maxn=1e6+10;queue<int>q;

int ed[151],fail[maxn],n,rt=1,id=1,ch[maxn][26],ans,vis[maxn],w[151];char s[151][maxn],ss[maxn];

void insert(char *s,int d)

{

	w[d]=strlen(s+1);rt=1;

	for(rg int i=1;i<=w[d];i++)

	{

		int now=s[i]-'a';

		if(!ch[rt][now])ch[rt][now]=++id;

		rt=ch[rt][now];

	}

	ed[d]=rt;

}

void bfs()

{

	q.push(1);

	while(!q.empty())

	{

		int x=q.front();q.pop();

		for(rg int i=0;i<26;i++)

		{

			if(!ch[x][i]){ch[x][i]=fail[x]?ch[fail[x]][i]:1;continue;}

			int j=fail[x],z=ch[x][i];q.push(z);

			while(j&&!ch[j][i])j=fail[j];

			if(j)fail[z]=ch[j][i];

			else fail[z]=1;

		}

	}

}

void solve()

{

	int j=1,len=strlen(ss+1);

	for(rg int i=1;i<=len;i++)

	{

		int now=ss[i]-'a';

		while(j&&!ch[j][now])j=fail[j];

		if(!ch[j][now])continue;j=ch[j][now];int k=j;

		while(k)vis[k]++,k=fail[k];

	}

	int  mx=0;

	for(rg int i=1;i<=n;i++)if(mx<vis[ed[i]])mx=vis[ed[i]];

	printf("%d\n",mx);

	for(rg int i=1;i<=n;i++)

		if(mx==vis[ed[i]]){for(rg int j=1;j<=w[i];j++)printf("%c",s[i][j]);printf("\n");}

}

int main()

{

	while(1)

	{

		read(n);if(!n)return 0;id=1;

		memset(ch,0,sizeof ch);

		memset(fail,0,sizeof fail);

		memset(vis,0,sizeof vis);

		for(rg int i=1;i<=n;i++)scanf("%s",s[i]+1),insert(s[i],i);

		bfs(),scanf("%s",ss+1),solve();

	}

}

巴特西

luoguP3796[模板]AC自动机（加强版）

传送门

最新文章

热门文章