灵异事件
查看原帖
灵异事件
1052371
jiangjiang12楼主2025/7/22 21:39

本地运行结果与洛谷评测机运行结果不一致。。。在洛谷评测机上我的代码第一个数字全部输出了0,但本地运行答案似乎是正确的???

#include <bits/stdc++.h>
using namespace std;
const int MAXN=155, MAXL=11005;
int N;
struct AC{
	string s[MAXN];
	int trie[MAXL][30], num[MAXL], fail[MAXL], ans[MAXN], node, N;
	AC(){
		for(int i=0; i<MAXL; i++){
			num[i]=fail[i]=0;
			for(int j=1; j<=26; j++){
				trie[i][j]=0;
			}
		}
		for(int i=1; i<MAXN; i++){
			ans[i]=0;
		}
	}
	void insert(string str, int ord){
		int key=0;
		for(int i=0; i<str.length(); i++){
			if(!trie[key][str[i]-96]){
				node++;
				trie[key][str[i]-96]=node;
			}
			key=trie[key][str[i]-96];
		}
		num[key]=ord;
	}
	void build(){
		for(int i=1; i<=N; i++){
			insert(s[i], i);
		}
		queue<int> q;
		for(int i=1; i<=26; i++){
			if(trie[0][i]){
				q.push(trie[0][i]);
			}
		}
		while(!q.empty()){
			int u=q.front(); q.pop();
			if(!fail[u]){
				fail[u]=0;
			}
			for(int i=1; i<=26; i++){
				if(trie[u][i]){
					fail[trie[u][i]]=trie[fail[u]][i];
					q.push(trie[u][i]);
				}else{
					trie[u][i]=trie[fail[u]][i];
				}
			}
		}
	}
	void query(string s0){
		int u=0, res=0;
		for(int i=0; i<s0.length(); i++){
			u=trie[u][s0[i]-96];
			for(int j=u; j&&num[j]; j=fail[j]){
				if(num[u]){ans[num[u]]++;}
			}
		}
	}
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	while(cin>>N){
		if(!N){break;}
		AC h;
		for(int i=1; i<=N; i++){
			cin>>h.s[i];
		}
		h.build();
		string ts; cin>>ts;
		h.query(ts); int Ans=0;
		for(int i=1; i<=N; i++){
			Ans=max(h.ans[i], Ans);
		}
		cout<<Ans<<endl;
		for(int i=1; i<=N; i++){
			if(Ans==h.ans[i]){
				cout<<h.s[i]<<endl;
			}
		}
	}
	
	return 0;
}
2025/7/22 21:39
加载中...