MgZn求助
查看原帖
MgZn求助
112395
Martin_MHT楼主2021/5/5 15:51

91pts, #9过不去, 求助, 不知道为什么无法下载数据.

#include <queue>
#include <cstdio>
#include <cstring>
#define M 160
#define N 1000010
#define fo(i, a, b) for(int i = (a); i <= (b); ++i)
#define fd(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
inline int read()
{
	int x = 0; char ch = getchar();
	while(ch < '0' || ch > '9')	ch = getchar();
	while(ch >= '0' && ch <= '9')	x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return x;
}
int n, cnt[M];
char s[M][70], st[N];
inline int max(int a, int b){return a > b ? a : b;}
namespace AC
{
	int tot, end[M * 70], tr[M * 70][26], fail[M * 70];
	void init()
	{
		tot = 0;
		fo(i, 1, n + 5)	memset(s[i], 0, sizeof(s[i]));
		fo(i, 0, n * 70 + 5)	end[i] = fail[i] = 0, memset(tr[i], 0, sizeof(tr[i]));
	}
	void insert(char *s, int len, int id)
	{
		int u = 0;
		for(int i = 0; i < len; ++i)
		{
			int p = s[i] - 'a';
			if(!tr[u][p])	tr[u][p] = ++tot;
			u = tr[u][p];
		}
		end[u] = id;
	}
	void build()
	{
		queue<int> q;
		fo(i, 0, 25)	if(tr[0][i])	q.push(tr[0][i]);
		while(!q.empty())
		{
			int u = q.front(); q.pop();
			fo(i, 0, 25)	tr[u][i] ? q.push(tr[u][i]), fail[tr[u][i]] = tr[fail[u]][i] : tr[u][i] = tr[fail[u]][i];
		}
	}
	int query(char *s, int len)
	{
		int cur = 0;
		for(int i = 0; i < len; ++i)
		{
			cur = tr[cur][s[i] - 'a'];
			for(int j = cur; j; j = fail[j])	++cnt[end[j]];
		}
	}
}
int main()
{
//	freopen("ac.in", "r", stdin);
//	freopen("ac.out", "w", stdout);
	while(1)
	{
		n = read();
		if(!n)	break ;
		fo(i, 1, n)	scanf("%s", s[i]), AC::insert(s[i], strlen(s[i]), i);
		AC::build();
		scanf("%s", st);
		AC::query(st, strlen(st));
		int ans = 0;
		fo(i, 1, n)	ans = max(ans, cnt[i]);
		printf("%d\n", ans);
		fo(i, 1, n)	cnt[i] == ans && (printf("%s\n", s[i]));
		AC::init();
		memset(cnt, 0, sizeof(cnt));
	}
	return 0;
}
2021/5/5 15:51
加载中...