【字典树】洛谷 P3879 [TJOI2010]阅读理解
2021/5/14 18:55:13
本文主要是介绍【字典树】洛谷 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]阅读理解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求