爆0求助
查看原帖
爆0求助
1029083
qhz114514楼主2024/10/16 21:31
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1000010;
int n,idx=0,ne[N],t[N][27],cnt[N];
char s[N];
//ne[u]:节点u回跳边的终点;t[u][c]:节点u树边的终点或转移边的终点(无儿子)
//cnt[i]:有几个单词以当前节点结尾 
//回跳边:当前节点父节点的回跳边所指节点的儿子(另一棵子树上的c的编号) 
//回跳边所指节点一定是当前节点到根路径上的最长后缀 
//转移边: 当前节点回跳边所指节点的儿子(另一棵子树上的c的儿子cc的编号)
void buildTrie(char *str){//建字典树 
    int x;
    for(int i=0;str[i];i++){
    	int y=str[i]-'a';
    	if(!t[x][y])t[x][y]=++idx;
    	x=t[x][y];
	}
	cnt[x]++;
}

void buildfail(){//建回跳边、转移边 
	queue<int>q;
	for(int i=0;i<26;i++)
		if(t[0][i])q.push(t[0][i]);//加入根的子节点
	while(!q.empty()){
		int x=q.front(),y;q.pop();
		for(int i=0;i<26;i++){
			y=t[x][i];//儿子的编号 
			if(y){
				ne[y]=t[ne[x]][i];
				q.push(y);//有儿子帮儿子构回跳边,并把儿子加入遍历 
			}
			else t[x][i]=t[ne[x]][i];//无儿子构转移边 
		}
	} 
}

int query(char *str){
	int ans=0;
	for(int k=0,i=0;str[k];k++){
		i=t[i][str[k]-'a'];//i节点编号 
		for(int j=i;j&&(~cnt[j]);j=ne[j]){//考虑当前节点后缀 
			ans+=cnt[j];//加上权值 
			cnt[j]=-1;//清空权值,防止权值累加,-1取反是0 
		} 
	}
	return ans;
} 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		buildTrie(s);
	}
	ne[0]=0;
	buildfail();
	scanf("%s",s);
	printf("%d\n",query(s));
	return 0;
}
2024/10/16 21:31
加载中...