Trie字典树,用单词匹配文章,全WA,求助
查看原帖
Trie字典树,用单词匹配文章,全WA,求助
95072
wudiss8楼主2021/8/3 09:08

RT,样例已经过了,用的gets,不知道会不会出pot,希望大佬帮助

#include<bits/stdc++.h>
#define rg register int
using namespace std;
char wor[31],pass[1001][5101];
int flag[510001],ch[510001][26],tot,ans[10021][1021];
inline void insert(int l,int bh){
	int x=1;
	for(rg i=0;i<l;i++){
		int s=wor[i]-'a';
		if(!ch[x][s])
		tot++,ch[x][s]=tot;
		x=ch[x][s];
	}
	flag[x]=bh;
}
inline void check(int bh){
	int x=1,l=strlen(wor);
	for(rg i=0;i<l;i++){
		int s=wor[i]-'a';
		if(!ch[x][s])return;
		x=ch[x][s];
    }
    ans[flag[x]][0]++;
    int ls=ans[flag[x]][0];
    ans[flag[x]][ls]=bh;
}
inline void chec(int bh){
	int l=strlen(pass[bh]);
	int zz=0;
	memset(wor,0,sizeof(wor));
	for(rg i=0;i<=l;i++){
		if(pass[bh][i]<'a' or pass[bh][i]>'z'){
			check(bh);
			zz=0;
			memset(wor,0,sizeof(wor));
		}else{
		    wor[zz]=pass[bh][i];
		    zz++;
	    }
	}
}
inline int read(){
	char c=getchar();
	int s=0,f=1;
	while(c<'0' or c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0' and c<='9'){
		s=(s<<1)+(s<<3)+c-'0';
		c=getchar();
	}
	return s*f;
}
int main(){
	int n,l,m;
	n=read();
	for(rg i=1;i<=n;i++){
		l=read();
		gets(pass[i]);
	}
	m=read();
	for(rg i=1;i<=m;i++){
		cin>>wor;
		insert(strlen(wor),i);
	}
	for(rg i=1;i<=n;i++){
		chec(i);
	}
	for(rg i=1;i<=m;i++){
		for(rg j=1;j<=ans[i][0];j++)printf("%d ",ans[i][j]);
		printf("\n");
	}
	return 0;
}
2021/8/3 09:08
加载中...