Java教程

【字典树】洛谷 P3879 [TJOI2010]阅读理解

本文主要是介绍【字典树】洛谷 P3879 [TJOI2010]阅读理解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题链

字典树模板题;

总结:字典树数组长度应大于等于所有字符串总和长度,数组最后一维取决于字符集的大小;

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 998244353
#define MAXN 1e18
#define MS 150000

int n,m;
int v[1009][5009];
int p[1009][5009][30];
char s[30];
int step;

void insert(int i){
	int h = strlen(s+1);
	int cc = 0;
	for(int k=1;k<=h;k++){
		int x = s[k]-'a'+1;
		if(!p[i][cc][x]) p[i][cc][x] = ++step;
		cc = p[i][cc][x];
	}
	v[i][cc]++;
}

void find(){
	int h = strlen(s+1);
	for(int i=1;i<=n;i++){
		int cc = 0;
		int flag = 1;
		for(int j=1;j<=h;j++){
			int x = s[j]-'a'+1;
			if(!p[i][cc][x]){
				flag = 0;
				break;
			}
			cc = p[i][cc][x];
		}
		if(!v[i][cc]) flag = 0;
		if(flag){
			cout << i << " ";
		}
	}
	cout << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> m;
		step = 0;
		for(int j=1;j<=m;j++){
			cin >> s+1;
			insert(i);
		}
	}
	cin >> m;
	while(m--){
		cin >> s+1;
		find();
	}
	
	
	return 0;
}
这篇关于【字典树】洛谷 P3879 [TJOI2010]阅读理解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!