首页 > 代码库 > 【字符串匹配】UVALive 4670 模板题

【字符串匹配】UVALive 4670 模板题

给一个文本T,和n个模板字符串,都是由小写字母组成,问这些字符串那些在字符串中出现的次数最多,输出最多的次数以及相应的字符串。

AC自动机的模板题,递归输出的时候改成累加次数统计数组cnt即可。

大白书认为会有重复出现的模板,但是在实际测试中,不判断重复也能通过。

#include<bits/stdc++.h>#define eps 1e-9#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 10505#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,big,cas,num,w,u,v;bool flag;char p[155][75];char t[1000006];struct ACauto{	int ch[MAXN][26];	int size;	int f[MAXN],last[MAXN],val[MAXN],cnt[MAXN];		void init()	{		size=1;		memset(ch[0],0,sizeof(ch[0]));		memset(cnt,0,sizeof(cnt));	}		int idx(char c)	{		return c-‘a‘;	}		void insert(char *s,int v)	{		int u=0,len=strlen(s);		for (int i=0;i<len;i++)		{			int c=idx(s[i]);			if (!ch[u][c])			{				memset(ch[size],0,sizeof(ch[size]));				val[size]=0;				ch[u][c]=size++;			}			u=ch[u][c];		}		val[u]=v;	}		void print(int j)	{		if (j)		{			cnt[val[j]]++;			print(last[j]);		}	}		int getFail()	{		queue <int> q;		f[0]=0;		for (int c=0;c<26;c++)		{			int u=ch[0][c];			if (u)			{				f[u]=0;				q.push(u);				last[u]=0;			}		}				while (!q.empty())		{			int r=q.front(); q.pop();			for (int c=0;c<26;c++)			{				int u=ch[r][c];				if (!u) 				{					ch[r][c]=ch[f[r]][c];					continue;				}				q.push(u);				int v=f[r];				f[u]=ch[v][c];				last[u]=val[f[u]]?f[u]:last[f[u]];			}		}	}						void find(char *T)	{		int n=strlen(T);		int j=0;		for (int i=0;i<n;i++)		{			int c=idx(T[i]);			while(j&&!ch[j][c]) j=f[j];			j=ch[j][c];			if (val[j]) print(j);			else if (last[j]) print(last[j]);		}	}}ac;int main(){	while (scanf("%d",&n),n)	{		ac.init();		for (i=1;i<=n;i++)		{			scanf("%s",p[i]);			ac.insert(p[i],i);		}		ac.getFail();		scanf("%s",t);		ac.find(t);				big=0;		for (i=1;i<=n;i++)		{			big=max(big,ac.cnt[i]); 		}		printf("%d\n",big);		for (i=1;i<=n;i++)		{			if (ac.cnt[i]==big) printf("%s\n",p[i]);		}	}	return 0;}

  

【字符串匹配】UVALive 4670 模板题