[dictionary tree] [trie] p3879 [tjoi2010] reading comprehension

P3879 [TJOI2010] reading comprehension

Dictionary tree writing

Reference resources 1

Reference resources 2

bitset usage

854ms/45.96MB

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;

int nex[300007][26],n,cnt=0;
bitset<1001> b[500007];//bool b[500007][1001];

void insert(char* s,int rol){
    
	int len=strlen(s+1);
    int now=0;
    FOR(i,1,len){
    
        int p=s[i]-'a';
        if(!nex[now][p])// If $Trie$ The tree is numbered without the prefix of this word 
			nex[now][p]=++cnt;// The number mentioned above  
        now=nex[now][p];// Then go deeper , Update the current location  
    }
    b[now][rol]=1;// This word is in the x There's a line 
}

void check(char* s){
    
	int len=strlen(s+1);
    int now=0,flag=1;
    FOR(i,1,len){
    
        int p=s[i]-'a';
        if(!nex[now][p]){
    // If in Trie There is no current character in the tree , You can do it directly break It fell off  
			flag=0;
			break;
		}
        now=nex[now][p];// Otherwise, update the location  
    }
    if(flag){
    
		FOR(i,1,n)// On the surface of the question, it is said to output in dictionary order  
			if(b[now][i]) cout<<i<<" ";// In which sentences does the output appear  
    }
    putchar('\n');
}

int main(){
    
    cin>>n;
    char s[25];
    FOR(i,1,n){
    
        int l;cin>>l;
        FOR(j,1,l){
    // Word by word insertion Trie In the tree  
        	cin>>(s+1);
			insert(s,i);
        }
    }
    int m;cin>>m;
    FOR(i,1,m){
    
    	cin>>(s+1);
		check(s);
    }
    return 0;
}

STL: MAP + VECTOR How to write it

Reference resources

use STL You don't have to worry about how big the array is and how big the space is , But it will take more time

2.06s/3.96MB

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;

const int maxn = 100001;
int n,m,num,cnt[maxn];
string s;
map<string,vector<int> >a;

int main(){
       
    cin>>n;
    FOR(i,1,n){
    
        cin>>num;
        FOR(j,1,num){
    
            cin>>s;
            a[s].push_back(i);// Every word is a vector, Save the number of sentences 
        }
    }
    cin>>m;
    FOR(i,1,m){
    
        cin>>s;
        mem(cnt);//cnt Is to remove the heavy bucket . Every time you use it to output different queries, you need to clear .
        int len=a[s].size();
        FOR(j,0,len-1)
            if(cnt[a[s][j]] == 0){
    
                cout<<a[s][j]<<" ";
                cnt[a[s][j]]++;// Remove weight with bucket 
            }
        cout<<endl;
    }
    return 0;
}

STL: MAP + SET How to write it

Reference resources

use set It can automatically remove the weight , More convenient . meanwhile Time consuming is excellent , Second only to handwriting Trie

972ms/5.34MB

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;

map<string,set<int> > m;

int main(){
    
    int n,p,l;
    string s;
    cin>>n;
    FOR(i,1,n){
    
        cin>>l;// The number of words 
        FOR(j,0,l-1){
    
            cin>>s;// word 
            m[s].insert(i);
        }
    }
    cin>>p;
    while(p--){
    
        cin>>s;
        if(m.count(s)){
    // If m There are elements in s
            for(auto iter=m[s].begin();iter!=m[s].end();++iter)
                cout<<*iter<<" ";
        }
        cout<<endl;
    }
    return 0;
}