字典树求调(样例能过但是全WA
查看原帖
字典树求调(样例能过但是全WA
313674
epiphanyer楼主2023/10/25 18:23
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;
const int maxn=5e6+5;
int trie[maxn][30],tot=1;
int head[maxn],ans[maxn],idx,nxt[maxn];
char a[25];
int T,n,m;
vector <int> pr;
void add(int id,int pas){
	ans[++idx]=pas;
	nxt[idx]=head[id];
	head[id]=idx;
}
void insert(char x[],int pas){
	int len=strlen(x),p=1;
	for(int i=0;i<len;i++){
		int ch=x[i]-'a';
		if(trie[p][ch]==0)trie[p][ch]=++tot;
		p=trie[p][ch];
	}
	add(p,pas);
}
void query(char x[]){
	int len=strlen(x),p=1;
	for(int i=0;i<len;i++){
		int ch=x[i]-'a';
		if(!trie[p][ch])break;
		p=trie[p][ch];
	}
	pr.clear();
	for(int i=head[p];i;i=nxt[i]){
		pr.push_back(i);
	}
	for(int i=pr.size()-1;i>=0;i--)printf("%d ",ans[pr[i]]);
	
}
int main(){
	scanf("%d",&T);
	for(int i=1;i<=T;i++){
		scanf("%d",&n);
		for(int j=1;j<=n;j++){
			scanf("%s",a+1);
			insert(a+1,i);
		}
	}
	scanf("%d",&m);
	while(m--){
		scanf("%s",a+1);
		query(a+1);
		if(m)printf("\n");
	}
	return 0;
}
2023/10/25 18:23
加载中...