不知哪里错了,求调
查看原帖
不知哪里错了,求调
369989
the_Soviet_Union楼主2021/5/4 17:13
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
queue<int> ffx;
char name[55],wbc[300000];
int cnt=0;
struct sckzs{
	int next;
	int fail;
	int mode;
	int length;//没什马用 
}a[500000][26];
inline void sckzs()
{
	int n;
	scanf("%d",&n);
	for(register int i=0;i<n;i++){
		scanf("%s",name);
		int len=strlen(name),j=0;
		for(register int k=0;k<len;k++){
			if(a[j][name[k]-'a'].next)j=a[j][name[k]-'a'].next;
			else{
				a[j][name[k]-'a'].next=cnt;	
				j=cnt++;
			}
		}
		a[j][name[len-1]-'a'].mode++;
		a[j][name[len-1]-'a'].length=len;
	}
}
inline void getfail()
{
	ffx.push(0);
	int j=0;
	while(!ffx.empty()){
		j=ffx.front();
		ffx.pop();
		for(register int i=0;i<26;i++){//所有子节点
			if(a[j][i].next){	
				for(register int l=0;l<26;l++){
					if(a[a[j][i].next][l].next){
						a[a[j][i].next][l].fail=a[j][l].fail;
						ffx.push(a[j][i].next);
					}
					else
						a[a[i][j].next][l].fail=a[i][j].fail;
				}
			}	
		} 
	}
}
inline void query()
{
	scanf("%s",wbc);
	int j=0;
	int len=strlen(wbc);
	for(register int i=0;i<len;i++)
	{
		if(a[j][wbc[i]-'a'].next){
			if(a[j][wbc[i]-'a'].mode){
				cnt+=a[j][wbc[i]-'a'].mode;
			}
			j=a[j][wbc[i]-'a'].next;
		}
		else{
			j=a[j][wbc[i]-'a'].fail;
		}
	}
}
int main()
{
	sckzs();
	getfail();
	query();
	printf("%d",cnt);
}
2021/5/4 17:13
加载中...