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

题链

字典树模板题；

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

#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;
}