fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int ALPHABET_SIZE = 26;
  6.  
  7. struct lowercase_string: string
  8. {
  9.     lowercase_string()
  10.     {
  11.         cin >> *this;
  12.     }
  13.  
  14.     int index(int i) const
  15.     {
  16.         return at(i)-'a';
  17.     }
  18. };
  19.  
  20. template<class T>
  21. struct strings: vector<T>
  22. {
  23.     strings()
  24.     {
  25.         size_t count; cin >> count, this->resize(count);
  26.     }
  27. };
  28.  
  29. struct index_vector: vector<int>
  30. {
  31.     int next(int i) const
  32.     {
  33.         size_t j = upper_bound(begin(),end(),i)-begin();
  34.  
  35.         return j == size() ? -1 : at(j);
  36.     }
  37. };
  38.  
  39. struct string_index: array<index_vector,ALPHABET_SIZE>
  40. {
  41.     string_index(const lowercase_string& s)
  42.     {
  43.         for (int n = s.size(), i = 0; i < n; ++i)
  44.             at(s.index(i)).push_back(i);
  45.     }
  46. };
  47.  
  48. template<class T,class U>
  49. struct trie: array<T*,ALPHABET_SIZE>
  50. {
  51.     trie()
  52.     {
  53.         this->fill(nullptr);
  54.     }
  55.  
  56.     void add_string(const U& s)
  57.     {
  58.         auto p = this;
  59.  
  60.         for (int n = s.size(), j, i = 0; i < n; ++i, p = p->at(j))
  61.             if (p->at(j=s.index(i)) == nullptr)
  62.                 p->at(j) = new T;
  63.     }
  64. };
  65.  
  66. template<class T>
  67. struct queries_trie: trie<queries_trie<T>,T>
  68. {
  69.     int count;
  70.  
  71.     queries_trie() : count(0) {}
  72.  
  73.     void add_subsequences(const string_index& i, int j = -1)
  74.     {
  75.         for (int k, l = 0; l < ALPHABET_SIZE; l++)
  76.             if (this->at(l) != nullptr and (k = i[l].next(j)) >= 0)
  77.                 this->at(l)->count++,
  78.                 this->at(l)->add_subsequences(i,k);
  79.     }
  80.  
  81.     void add_subsequences(const T& s)
  82.     {
  83.         add_subsequences(string_index(s));
  84.     }
  85.  
  86.     int matched_subsequences(const T& s) const
  87.     {
  88.         auto p = this;
  89.  
  90.         for (int n = s.size(), i = 0; i < n; ++i)
  91.             p = p->at(s.index(i));
  92.  
  93.         return p->count;
  94.     }
  95. };
  96.  
  97. int main()
  98. {
  99.     ios_base::sync_with_stdio(false),
  100.     cin.tie(nullptr), cout.tie(nullptr);
  101.  
  102.     strings<lowercase_string> input, query;
  103.  
  104.     queries_trie<lowercase_string> t;
  105.  
  106.     for(auto s: query)
  107.         t.add_string(s);
  108.  
  109.     for(auto s: input)
  110.         t.add_subsequences(s);
  111.  
  112.     for(auto s: query)
  113.         cout << t.matched_subsequences(s) << '\n';
  114. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5
aeh
apoq
xyzq
alpqh
caqwerh
3
ah
a
b
stdout
copy 
3
4
0
https://ideone.com/FiJM78
String Subsequence Matching
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!