当前位置:网站首页>Dictionary tree simple introductory question (actually blue question?)
Dictionary tree simple introductory question (actually blue question?)
2022-07-05 21:00:00 【Soup key TJ】
[TJOI2010] reading comprehension
Title Description
The English teacher left N N N A reading comprehension assignment , But every English essay has many new words to look up in the dictionary , To save time , Now let's do a statistic , Let's count some new words that have appeared in some essays .
Input format
The first line is an integer N N N , Indicates the number of short articles , Each essay contains only spaces and lowercase letters .
Pressed down N N N That's ok , Each line describes a short passage . The beginning of each line is an integer L L L , This passage is written by L L L One word makes up .
Next is L L L Word , Separate words with a space .
Then it is an integer M M M , It means to ask several times . In the back M M M That's ok , Each line represents a new word to be counted .
Output format
Output one line for each new word , Count the number of essays in which it has appeared , And output the serial number of the passage from small to large , The serial number should not be repeated , The serial numbers are separated by a space ( Note that there should be no spaces in front of the first sequence number and after the last sequence number ). If the word has never appeared , Then output a blank line .
Examples #1
The sample input #1
3
9 you are a good boy ha ha o yeah
13 o my god you like bleach naruto one piece and so do i
11 but i do not think you will get all the points
5
you
i
o
all
naruto
Sample output #1
1 2 3
2 3
1 2
3
2
Tips
about 30 % 30\% 30% The data of , 1 ≤ M ≤ 1 0 3 1\le M\le 10^3 1≤M≤103 .
about 100 % 100\% 100% The data of , 1 ≤ M ≤ 1 0 4 1\le M\le 10^4 1≤M≤104, 1 ≤ N ≤ 1 0 3 1\le N\le 10^3 1≤N≤103 .
The length of each essay ( Contain spaces between adjacent words ) ≤ 5 × 1 0 3 \le 5\times 10^3 ≤5×103 character , The length of each word ≤ 20 \le 20 ≤20 character .
Time limit of each test point 2 2 2 second .
All processes are in the notes
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long ll;
int son[N][30],idx,n,l,m;
char a[N];
bitset<1010> sign[N];
// use bool Explosive space
// use bool One value accounts for 1 byte ,1 Bytes are 8 The bit
// use bitset Then each bool Value takes only one bit , Greatly save space
void insert(char str[],int k){
// Insert string , At the same time, tell me which line it is
int p=0; // Traverse the insert from the root node
int l=strlen(str);
for(int i=0;i<l;i++){
int u=str[i]-'a'; // Convenience as a subscript
if(!son[p][u]) son[p][u]=++idx;
// View the current node p Child nodes of u Whether the number has been given , If there is no mark, it will be numbered
p=son[p][u];// Move to the next node conversion position
}
sign[p][k]=1;// Mark that the string exists in k That's ok
}
void find(char str[]){
// Find the string
int p=0,signsign=1;// initialization , Go back to the root node and continue to check
int l=strlen(str);
for(int i=0;i<l;i++){
// Traverse the nodes to query
int u=str[i]-'a';
if(!son[p][u]){
// Once found unmarked , Then the string... Does not exist , Exit traversal query
signsign=0;// At the same time, the tag does not exist
break;
}
p=son[p][u];// Move to the next node conversion position
}
if(signsign){
// Judge whether the query is successful by marking
for(int i=1;i<=n;i++){
if(sign[p][i]){
// Check whether this string exists in this line through the tag
printf("%d ",i);
}
}printf("\n");
}
else{
puts("");
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>l;
for(int j=1;j<=l;j++){
scanf("%s",a);
insert(a,i);
}
}
cin>>m;
for(int i=1;i<=m;i++){
scanf("%s",a);
find(a);
}
return 0;
}
边栏推荐
- 最长摆动序列[贪心练习]
- How to renew NPDP? Here comes the operation guide!
- 启牛2980有没有用?开户安全吗、
- 木板ISO 5660-1 热量释放速率摸底测试
- 如何让化工企业的ERP库存账目更准确
- Influence of oscilloscope probe on measurement bandwidth
- Utils/index TS tool function
- 序列联配Sequence Alignment
- Abnova DNA marker high quality control test program
- 基于AVFoundation实现视频录制的两种方式
猜你喜欢
Talk about my fate with some programming languages
EN 438-7建筑覆盖物装饰用层压板材产品—CE认证
解读协作型机器人的日常应用功能
Clion-MinGW编译后的exe文件添加ico图标
MySQL InnoDB架构原理
leetcode:1755. 最接近目标值的子序列和
Phpstudy Xiaopi's MySQL Click to start and quickly flash back. It has been solved
显示器要申请BS 476-7 怎么送样?跟显示屏一样吗??
基于vertx-web-sstore-redis的改造实现vertx http应用的分布式session
Research and development efficiency improvement practice of large insurance groups with 10000 + code base and 3000 + R & D personnel
随机推荐
The reason why the ncnn converted model on raspberry pie 4B always crashes when called
LeetCode: Distinct Subsequences [115]
解析五育融合之下的steam教育模式
Duchefa p1001 plant agar Chinese and English instructions
请查收.NET MAUI 的最新学习资源
100 cases of shell programming
Is it necessary for bazel to learn
Sequence alignment
10000+ 代码库、3000+ 研发人员大型保险集团的研发效能提升实践
教你自己训练的pytorch模型转caffe(一)
Who the final say whether the product is good or not? Sonar puts forward performance indicators for analysis to help you easily judge product performance and performance
Clear app data and get Icon
LeetCode_哈希表_困难_149. 直线上最多的点数
AITM 2-0003 水平燃烧试验
ts 之 属性的修饰符public、private、protect
Binary search
使用WebAssembly在浏览器端操作Excel
显示器要申请BS 476-7 怎么送样?跟显示屏一样吗??
Use of thread pool
Interpreting the daily application functions of cooperative robots