求助,超时了一个点
查看原帖
求助,超时了一个点
308583
跳跳谷hj楼主2020/12/26 14:53
#include<bits/stdc++.h>
using namespace std;
int t,n,tot,trie[1000100][27],wd[1000010],nxt[1000010];
string ss;
void insert(string s){
	int p=0;
	for(int i=0;i<s.size();i++){
		int c=s[i]-'a';
		if(!trie[p][c])trie[p][c]=++tot;
		p=trie[p][c];
	}
	wd[p]++;
}
void getfail(){
	queue<int> q;
	for(int i=0;i<26;i++){
		if(trie[0][i]){
			nxt[trie[0][i]]=0;
			q.push(trie[0][i]);
		}
	}
	while(!q.empty()){
		int p=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(trie[p][i]){
				nxt[trie[p][i]]=trie[nxt[p]][i];
				q.push(trie[p][i]);
			}else{
				trie[p][i]=trie[nxt[p]][i];
			}
		}
	}
}
int find(string s){
	int ans=0,p=0;
	for(int i=0;i<s.size();i++){
		int c=s[i]-'a';
		int k=trie[p][c];
		while(k>0){
			ans+=wd[k];
			wd[k]=0;
			k=nxt[k];
		}
		p=trie[p][c];
	}
	return ans;
}
int main(){
//	scanf("%d",&t);
//	while(t--){
		memset(trie,0,sizeof(trie));
		memset(wd,0,sizeof(wd));
		memset(nxt,0,sizeof(nxt));
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			cin>>ss;
			insert(ss);
		}
		getfail();
		cin>>ss;
		printf("%d\n",find(ss));
//	}
	return 0;	
}

有没有奆佬帮忙优化一下

2020/12/26 14:53
加载中...