AC自动机求调
查看原帖
AC自动机求调
257173
rish楼主2024/12/18 13:46

只对了第一个和最后一个测试点,其他全WA

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int n, tot = 1, Maxn, cnt;
int a[N][30], nxt[N], d[N], vis[N], ans[N];
char ss[N][100];
void insert(char *s, int num)
{
	int u = 1, len = strlen(s);
	for(int i=0;i<len;i++)
	{
		int ch = s[i]-'a';
		if(!a[u][ch]) a[u][ch] = ++tot, fill(a[tot], a[tot]+30, 0);
		u = a[u][ch];
	}
	d[u] = num;
}
void bfs()
{
	for(int i=0;i<=25;i++) a[0][i] = 1;
	nxt[1] = 0;
	nxt[0] = 1;
	queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i=0;i<=25;i++)
		{
			if(!a[u][i]) a[u][i] = a[nxt[u]][i];
			else q.push(a[u][i]), nxt[a[u][i]] = a[nxt[u]][i];
		}
	}
	return;
}
void find(char *s)
{
	int u = 1, len = strlen(s);
	for(int i=0;i<len;i++)
	{
		int ch = s[i]-'a', v = a[u][ch];
		for(int k=v;k>1;k=nxt[k]) ++vis[d[k]];
		u = v;
	}
}
int main()
{
	while(cin >> n, n)
	{
		memset(nxt, 0, sizeof(nxt));
		memset(vis, 0, sizeof(vis));
		memset(d, 0, sizeof(d));
		memset(a, 0, sizeof(a));
		for(int i=0;i<=25;i++) a[0][i] = 1;
		nxt[0] = 1;
		tot = 1;
		for(int i=1;i<=n;i++)
		{
			scanf("%s", &ss[i]);
			insert(ss[i], i);
		}
		bfs();
		scanf("%s", &ss[0]);
		find(ss[0]);
		Maxn = 0;
		for(int i=1;i<=n;i++) if(vis[i]>Maxn) Maxn = vis[i];
		cout << Maxn << endl;
		for(int i=1;i<=n;i++) if(vis[i]==Maxn) cout << ss[i] << endl;
	}
	return 0;
}
2024/12/18 13:46
加载中...