题目描述

有 \(N\) 个由小写字母组成的模式串以及一个文本串 \(T\) 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 \(T\) 中出现的次数最多。

输入输出格式

输入格式：

输入含多组数据。

每组数据的第一行为一个正整数 \(N\) ，表示共有 \(N\) 个模式串， \(1 \leq N \leq 150\) 。

接下去 \(N\) 行，每行一个长度小于等于 \(70\) 的模式串。下一行是一个长度小于等于 \(10^6\) 的文本串 \(T\) 。

输入结束标志为 \(N=0\) 。

输出格式：

对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

输入输出样例

输入样例#1：

2

aba

bab

ababababac

6

beta

alpha

haha

delta

dede

tata

dedeltalphahahahototatalpha

0

输出样例#1：

4

aba

2

alpha

haha

题解

同样的，简单匹配，匹配到有结尾标记的点，就把标记的点的贡献加上

最后取个最大值，找串输出就好了

因为可能存在相同的串，结尾标记用vector存就好了

#include<bits/stdc++.h>

#define ui unsigned int

#define ll long long

#define db double

#define ld long double

#define ull unsigned long long

const int MAXN=150+10,MAXS=1000000+10,MAXM=15000+10;

int n,ch[MAXM][30],fail[MAXM],last[MAXM],ed[MAXM],ans[MAXN],cnt;

char s[MAXS],t[MAXN][80];

std::queue<int> q;

std::vector<int> V[MAXM];

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();

	x=data*w;

}

template<typename T> inline void write(T x,char ch='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(ch!='\0')putchar(ch);

}

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

inline void init()

{

	for(register int i=0,lt=strlen(s);i<lt;++i)s[i]-='a'-1;

}

inline void insert(int rk)

{

	int x=0;

	for(register int i=0,lt=strlen(s);i<lt;++i)

		if(!ch[x][s[i]])x=ch[x][s[i]]=++cnt;

		else x=ch[x][s[i]];

	ed[x]=1;

	V[x].push_back(rk);

}

inline void getfail()

{

	for(register int i=1;i<=26;++i)

		if(ch[0][i])q.push(ch[0][i]);

	while(!q.empty())

	{

		int x=q.front();

		q.pop();

		for(register int i=1,y,z;i<=26;++i)

			if(ch[x][i])

			{

				y=ch[x][i],z=fail[x];

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

				fail[y]=ch[z][i];

				last[y]=ed[fail[y]]?fail[y]:last[fail[y]];

				q.push(y);

			}

			else ch[x][i]=ch[fail[x]][i];

	}

}

inline void save(int x)

{

	if(x)

	{

		if(ed[x])

			for(register int i=0,lt=V[x].size();i<lt;++i)ans[V[x][i]]++;

		save(last[x]);

	}

}

inline void match()

{

	int x=0;

	for(register int i=0,lt=strlen(s);i<lt;++i)x=ch[x][s[i]],save(ed[x]||last[x]?x:0);

}

int main()

{

	while(scanf("%d",&n)!=EOF&&n)

	{

		for(register int i=1;i<=cnt;++i)V[i].clear();

		memset(ch,0,sizeof(ch));

		memset(ed,0,sizeof(ed));

		memset(ans,0,sizeof(ans));

		memset(fail,0,sizeof(fail));

		memset(last,0,sizeof(last));

		cnt=0;

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

		{

			scanf("%s",s);

			memcpy(t[i],s,sizeof(t[i]));

			init();insert(i);

		}

		getfail();

		scanf("%s",s);init();match();

		int len=0;

		for(register int i=1;i<=n;++i)chkmax(len,ans[i]);

		write(len,'\n');

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

			if(ans[i]==len)puts(t[i]);

	}

	return 0;

}

巴特西

【刷题】洛谷 P3796 【模板】AC自动机（加强版）

题目描述

输入输出格式

输入输出样例

题解

最新文章

热门文章