萌新求助,大佬们帮帮我谢谢
  • 板块灌水区
  • 楼主封禁用户
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/9 10:17
  • 上次更新2023/11/9 14:33:48
查看原帖
萌新求助,大佬们帮帮我谢谢
1183222
封禁用户楼主2023/11/9 10:17
//P3879 [TJOI2010] 阅读理解

/*

	字典树,每次insert时候维护一个二维数组,这个单词在哪行出现了
	 

*/

#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn = 5e3 + 5;
int tire[maxn][26];
int tot;
bool vis[maxn][1005];//标记这个单词在这行出现没 
string s;

void insert(int x){
	cin >> s;
	int p = 0;
	for (int i = 0; i < s.size(); i++){
		if (tire[p][s[i] - 'a'] == 0){
			tire[p][s[i] - 'a'] = ++tot;
		}
		p = tire[p][s[i] - 'a'];
	}
	vis[p][x] = 1;//标记 
} 

void find() {
	string str;
	cin >> str;
	int p = 0;
	bool flag = 1;
	for (int i = 0; i< str.size(); i++){
		if (tire[p][str[i]-'a']==0){
//			cout << '\n';
//			return ;
			flag = 0;
			break;
		}
		p = tire[p][str[i] - 'a'];
	}
	if(flag){
		for (int i = 1;i <= n; i++){
			if (vis[p][i]){
				cout << i <<" ";
			}
		}
	}
	cout << endl;
}

int main () {
	cin >> n;
	for (int i = 1; i <= n;i++){
		int l;
		cin >> l;
		for (int i = 1;i <= l; i++){
			insert(i);//第i行 
		}
	}
	
	int m;
	cin >> m;
	for (int i = 1;i <= m ; i++){
		find();
	}
	return 0;
}
2023/11/9 10:17
加载中...