字典树萌新。WA求助
查看原帖
字典树萌新。WA求助
338786
mushroom_knight楼主2020/12/22 17:39

RT,我知道不能用二位数组去存 end[]end[]

但是这个普通做发没有输出,求神仙看一看QAQ


#include<bits/stdc++.h>
using namespace std;

namespace Trie{
	const int si=3e5+10;
	const int k=26;
	int trie[si][k];
	int end[1000][si];
	int tot=0;
	
	inline int calid(char x){
		return x-'a';
	}
	
	void insert(string str,int pos){
	    int len=str.size();
	    int p=1;
	    for(register int k=0;k<len;++k){
	        int ch=calid(str[k]);
	        if(trie[p][ch]==0){
	            trie[p][ch]=++tot;    
	        }
	        p=trie[p][ch];    
	    }
	    end[pos][p]++;
	}
	
	int search(string str,int pos){ 
	    int len=str.size();
	    int p=1;
	    for(register int k=0;k<len;++k){
	        p=trie[p][str[k]-'a'];
	        if(p==0){
	            return 0;
	        }
	    }
	    return end[pos][p];
	}
}

int n,m;
string input;
int L;
int cnt;

int main(){
	scanf("%d",&n);
	while(n--){
		++cnt;
		scanf("%d",&L);
		for(register int i=1;i<=L;++i){
			cin>>input;
			Trie::insert(input,cnt);
		}	
	}
	scanf("%d",&m);
	for(register int i=1;i<=m;++i){
		cin>>input;
		for(register int i=1;i<=n;++i){
			int res=Trie::search(input,i);
			if(res){
				printf("%d ",res);
			}
		}
		puts("");
	}
	return 0;
}

2020/12/22 17:39
加载中...