Dictionary tree simple introductory question (actually blue question?)

[TJOI2010] reading comprehension

Title Description

The English teacher left $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$ , Indicates the number of short articles , Each essay contains only spaces and lowercase letters .

Pressed down $N$ That's ok , Each line describes a short passage . The beginning of each line is an integer $L$ , This passage is written by $L$ One word makes up .

Next is $L$ Word , Separate words with a space .

Then it is an integer $M$ , It means to ask several times . In the back $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\%$ The data of , $1\le M\le 10^3$ .

about $100\%$ The data of ,$1\le M\le 10^4$,$1\le N\le 10^3$ .

The length of each essay （ Contain spaces between adjacent words ）$\le 5\times 10^3$ character , The length of each word $\le 20$ character .

Time limit of each test point $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;
}