蒟蒻调傻了,求助大佬
查看原帖
蒟蒻调傻了,求助大佬
67618
haooo楼主2020/12/1 22:00
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define RT register
#define ll long long
using namespace std;
const int MAXN=55;
template <typename T>
inline void read(T &x){
	x=0; bool f=0; char ch=getchar();
	while(ch<'0'||ch>'9'){f|=ch=='-'; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}
	x=f? -x:x;
}
template <typename T>
inline void print(T x){
	if(x<0) x=-x,putchar('-');
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
int n;
int tot[MAXN];
string str[55];
string a;
struct Aho{
	int siz,son[26][MAXN],fail[MAXN],cnt[MAXN];
	const int root=0;
	inline void Init(){
		siz=0;
		memset(son,0,sizeof(son));
		memset(cnt,0,sizeof(cnt));
		memset(fail,0,sizeof(fail));
	}
	inline void Insert(string s,int id){
		int len=s.size();
		int now=root;
		for(int i=0;i<len;i++){
			if(!son[s[i]-'a'][now]) son[s[i]-'a'][now]=++siz;
			now=son[s[i]-'a'][now];
		}
		cnt[now]=id;
	}
	inline void GetFail(){
		queue<int> q;
		for(int i=0;i<26;i++) if(son[i][root]) fail[son[i][root]]=root,q.push(son[i][root]);
		while(!q.empty()){
			int now=q.front();q.pop();
			for(int i=0;i<26;i++){
				if(son[i][now]) fail[son[i][now]]=son[i][fail[now]],q.push(son[i][now]);
				else son[i][now]=son[i][fail[now]];
			}
		}
	}
	inline void Match(string s){
		int len=s.size();
		int now=root;
		for(int i=0;i<len;i++){
			now=son[s[i]-'a'][now];
			for(int t=now;t;t=fail[t]) if(cnt[t]) tot[cnt[t]]++;
		}
	}
}aho;
int main(){
	while(cin>>n&&n){
		aho.Init();
		memset(tot,0,sizeof(tot));
		for(int i=1;i<=n;i++){
			cin>>str[i];
			aho.Insert(str[i],i);
		}
		
		cin>>a;
		aho.Match(a);
		int maxn=0;
		for(int i=1;i<=n;i++) maxn=max(tot[i],maxn);
//		for(int i=1;i<=n;i++) cout<<s[i]<<" "<<tot[i]<<"\n";
		cout<<maxn<<"\n";
		for(int i=1;i<=n;i++)
			if(maxn==tot[i])
				cout<<str[i]<<"\n";
	}
	return 0;
}

连样例都没过,已经查了连续3天了(,连同学都没找出错来/kk/kk

2020/12/1 22:00
加载中...