Trie 0pts 求调
查看原帖
Trie 0pts 求调
1023793
yaodiguoan楼主2024/8/6 18:04

recordrecord

思路是给每一句话开一个 trie,然后暴力查询

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")
#define hh putchar('\n')
#define kg putchar(' ')
#define debug puts("debug")
//#define int long long
//#define int __int128
namespace quickread{
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void write(T x){
		if(x<0) putchar('-'),x=~x+1;
		if(x>9) write(x/10);
		putchar(x%10^48);
	}
	inline string readstr(){
    	char ch=getchar();string str="";
		while(!isalnum(ch)) ch=getchar();
		while(isalnum(ch)){str+=ch;ch=getchar();}
		return str;
	}
	inline char readchar(){
		char ch=getchar();
		while(!isalnum(ch)) ch=getchar();
		return ch;
	}
}
using namespace quickread;
const int N=1e3+10,inf=2147483647;
struct Trie{
	int cnt=0;
	struct node{int nex[30];bool tag;node(){memset(nex,0,sizeof(nex)),tag=0;}};
	node tree[N];
	void update(string s){
		int len=s.length(),p=1;
		for(int i=0;i<len;++i){
			int ch=s[i]-'a'+1;
			if(!tree[p].nex[ch]) tree[p].nex[ch]=++cnt;
			p=tree[p].nex[ch];
		}
		tree[p].tag=1;
	}
	bool query(string s){
		int len=s.length(),p=1;
		for(int i=0;i<len;++i){
			int ch=s[i]-'a'+1;
			if(!tree[p].nex[ch]) return 0;
			p=tree[p].nex[ch];
		}
		return tree[p].tag;
	}
} trie[N];
int n,m;
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	read(n);
	for(int i=1;i<=n;++i) {
		int k;read(k);
		while(k--) {string s=readstr();trie[i].update(s);}
	}
	read(m);
	while(m--){
		string s=readstr();
		for(int i=1;i<=n;++i)
			if(trie[i].query(s)) write(i),kg;
		hh;
	}
	return 0;
}


2024/8/6 18:04
加载中...