求助,为什么re?
查看原帖
求助,为什么re?
191956
珂朵莉!楼主2021/6/12 14:36

两个点都re,球球大佬们帮帮忙吧

#include<bits/stdc++.h>
using namespace std;
int trie[10000005][26],color[10000005],num=1,fail[10000005];
void add_string(string adds){
	int len=adds.length();
	int p=1;
	for(int i=0;i<len;i++){
		if(!trie[p][adds[i]-'a'])
			trie[p][adds[i]-'a']=++num;
		p=trie[p][adds[i]-'a'];
	}
	color[p]++;
}
void getfail(){
	for(int i=0;i<=25;i++)
		trie[0][i]=1;
	int q[100005];
	q[1]=1;
	fail[1]=0;
	for(int tail=1,head=1;head<=tail;head++){
		int u=q[head];
		for(int i=0;i<=25;i++){
			if(!trie[u][i])
				trie[u][i]=trie[fail[u]][i];
			else{
				int v=fail[u];
				q[++tail]=v;
				fail[trie[u][i]]=trie[v][i];
			}
		}
	}
	//cout<<num<<endl;
	//for(int i=1;i<=num;i++)cout<<fail[i]<<endl; 
}
int find(string main_string){
	int u=1,ans=0;
	for(int i=0;i<main_string.length();i++){
		int c=main_string[i]-'a';
		int k=trie[u][c];
		while(k>1){
			ans+=color[k];
			color[k]=0;
			k=fail[k];
		}
		u=trie[u][c];
	}
	return ans;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string inp;
		cin>>inp;
		add_string(inp);
	}
	string m;
	getfail();
	cin>>m;
	cout<<find(m);
}
2021/6/12 14:36
加载中...