社区讨论

求助,是不是数组大小有问题

P3796AC 自动机(简单版 II)参与者 4已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@mi6x9bbr
此快照首次捕获于
2025/11/20 12:19
4 个月前
此快照最后确认于
2025/11/20 12:19
4 个月前
查看原帖
RE了大部分点,开大了却又WA了
CPP
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 155;
int n;
char str[maxn][maxn];
struct AC_automation{
	int ch[maxn][26],val[maxn],fail[maxn],trank[maxn],cnt;
	queue<int>q;
	//s从1开始
	void clear (){
		cnt=0;
		memset(ch,0,sizeof(ch));
		memset(val,0,sizeof(val));
		memset(fail,0,sizeof(fail));
		memset(trank,0,sizeof(trank));
	}
	void insert (char *s,int id){
		int now=0,v;
		while (*(++s)){
			v=(*s)-'a';
			if (!ch[now][v]) ch[now][v]=++cnt;
			now=ch[now][v];
		}
		val[now]++,trank[now]=id;
	}
	void build (){
		for (int i=0;i<=25;i++)	
			if (ch[0][i])
				fail[ch[0][i]]=0,q.push(ch[0][i]);
		while (!q.empty()){
			int u=q.front();
			q.pop();
			for (int i=0;i<=25;i++){
				if (ch[u][i])	fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
				else ch[u][i]=ch[fail[u]][i];
			}
		}
	}
	//s从1开始
	void query (char *s){
		int ans[maxn],last[maxn][151],now=0,v,mx=-1;
		for (int i=0;i<26;i++)ans[i]=0;
		for (int i=0;i<maxn;i++)last[i][0]=0;
		while (*(++s)){
			v=(*s)-'a';
			now=ch[now][v];
			int temp=now;
			while (temp){
				if (val[temp]){
					ans[trank[temp]]+=val[temp];
					mx=max(mx,ans[trank[temp]]);
					last[ans[trank[temp]]][++last[ans[trank[temp]]][0]]=trank[temp];
					
				}
				temp=fail[temp];
			}
		}
		printf("%d\n",mx);
		sort(last[mx]+1,last[mx]+last[mx][0]+1);
		for (int i=1;i<=last[mx][0];i++)
		printf("%s\n",str[last[mx][i]]+1);
	}
}AC;
int main ()
{
	scanf("%d",&n);
	while(n){
		AC.clear();
		for (int i=1;i<=n;i++)	scanf("%s",str[i]+1),AC.insert(str[i],i);
		AC.build();
		scanf("%s",str[0]+1);
		AC.query(str[0]);
		scanf("%d",&n);
	}
	return 0;
}

回复

10 条回复,欢迎继续交流。

正在加载回复...