fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN=1e6+5;
  5. int n, q;
  6. string s;
  7.  
  8. struct node{
  9.     node* child[26];
  10.     int fi;
  11.     vector<int> pos;
  12.     node(){
  13.         fi=-1;
  14.         for (int i=0; i<26; i++){
  15.             child[i]=nullptr;
  16.         }
  17.     }
  18. };
  19.  
  20. struct Trie{
  21.     Trie(){}
  22.  
  23.     node* createNode()
  24.     {
  25.         return new node();
  26.     }
  27.  
  28.     node* root=createNode();
  29.  
  30.     void addStr(const string &s, int id)
  31.     {
  32.         node* p=root;
  33.         for (int i=0; i<(int)s.length(); i++){
  34.             int c=s[i]-'a';
  35.             if(p->child[c]==nullptr) p->child[c]=createNode();
  36.             p=p->child[c];
  37.             p->pos.push_back(id);
  38.         }
  39.         if(p->fi==-1) p->fi=id;
  40.     }
  41.  
  42.     int Find(const string &s)
  43.     {
  44.         node* p=root;
  45.         for (int i=0; i<(int)s.length(); i++){
  46.             int c=s[i]-'a';
  47.             if(p->child[c]==nullptr) return -1;
  48.             p=p->child[c];
  49.         }
  50.         return p->fi;
  51.     }
  52.  
  53.     int calc(const string &s, int id)
  54.     {
  55.         int res=0;
  56.         node* p=root;
  57.         for (int i=0; i<(int)s.length(); i++){
  58.             int c=s[i]-'a';
  59.             if(p->child[c]==nullptr){
  60.                 break;
  61.             }
  62.             p=p->child[c];
  63.             auto it=upper_bound(p->pos.begin(), p->pos.end(), id);
  64.             res+=(it-p->pos.begin());
  65.         }
  66.         return res;
  67.     }
  68. }TRIE;
  69.  
  70. int main()
  71. {
  72.     ios_base::sync_with_stdio(0);
  73.     cin.tie(0); cout.tie(0);
  74.     cin >> n;
  75.     for (int i=1; i<=n; i++){
  76.         cin >> s;
  77.         TRIE.addStr(s, i);
  78.     }
  79.     cin >> q;
  80.     while(q--){
  81.         cin >> s;
  82.         int id=TRIE.Find(s);
  83.         if(id==-1){
  84.             id=n;
  85.         }
  86.         cout << id+TRIE.calc(s, id) << "\n";
  87.     }
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/6uzpRp
language:
C++ (gcc 8.3)
created:
12 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!