fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int NN = 112;
  5. const int MM = 512;
  6.  
  7. string msg[NN][MM],pat;
  8. int Len[NN],N,M;
  9.  
  10. int LPS[NN],aut[NN][2];
  11. int G[NN][NN],K[NN][NN];
  12.  
  13. /*
  14.    G[i][j] -> next state if cur state i and string j encountered (state = match)
  15.    K[i][j] -> no of matches found if state = i, and string = j encountered
  16. */
  17.  
  18. bool alpha(string ch){ return (ch.size() <= 1 and (ch[0] == 'a' or ch[0] == 'b')); }
  19. int conv(char x){
  20.     if (x == 'a' or x == 'b') return (int)(x-'a');
  21.     return (int)(x-'0');
  22. }
  23.  
  24. int conv(string x){
  25.     if (alpha(x))
  26.         return conv(x[0]);
  27.     int ans = 0;
  28.     for(int i = 0; i < (int)x.size(); ++i)
  29.         ans = ans*10 + conv(x[i]);
  30.     assert(ans >= 1 and ans <= N);
  31.     return ans;
  32. }
  33.  
  34. void build_kmp(int n){
  35.     int k = LPS[0] = 0;
  36.     for(int i = 1; i < n; ++i){
  37.         while(k > 0 and pat[k] != pat[i])
  38.             k = LPS[k-1];
  39.         LPS[i] = (k += (pat[k] == pat[i]));
  40.     }
  41. }
  42.  
  43. void build_aut(int n){
  44.     for(int i = 0; i <= n; ++i) for(int k = 0; k < 2; ++k){
  45.         if (i > 0 and k != conv(pat[i]))
  46.             aut[i][k] = aut[LPS[i-1]][k];
  47.         else
  48.             aut[i][k] = i + (k == conv(pat[i]));
  49.     }
  50. }
  51.  
  52. void build_nxt(int n,int m){
  53.     for(int i = 1; i <= n; ++i) for(int j = 0; j <= m; ++j){
  54.         int ans = j, cnt = 0;
  55.         for(int k = 0; k < Len[i]; ++k){
  56.             int inp = conv(msg[i][k]);
  57.             if (alpha(msg[i][k])){
  58.                 ans = aut[ans][inp];
  59.                 cnt += (ans == m);
  60.             } else {
  61.                 cnt += K[ans][inp];
  62.                 ans = G[ans][inp];
  63.             }
  64.         }
  65.         G[j][i] = ans, K[j][i] = cnt;
  66.     }
  67. }
  68.  
  69. void solve(){
  70.     cin >> N >> pat;
  71.     M = (int)(pat.size());
  72.     pat.push_back('$');
  73.  
  74.     for(int i = 1; i <= N; ++i){
  75.         cin >> Len[i];
  76.         for(int j = 0; j < Len[i]; ++j)
  77.             cin >> msg[i][j];
  78.     }
  79.  
  80.     build_kmp(M);
  81.     build_aut(M);
  82.     build_nxt(N,M);
  83.     cout << K[0][N] << "\n";
  84. }
  85.  
  86. int main()
  87. {
  88.     ios_base::sync_with_stdio(false);
  89.     solve();
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0s 3804KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/NcBqKX
language:
C++ (gcc 8.3)
created:
10 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!