fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. const int N = 1e6;
  3. const int M = 1e3;
  4. #define ll long long
  5. const ll MOD = 1e9+7;
  6. const ll base = 31;
  7. using namespace std;
  8.  
  9. int n, q;
  10.  
  11. ll p[N+3], f[M+3][M+3];
  12. ll b[N+3];
  13.  
  14. ll get(int l, int r, int i){
  15.     ll res = (f[i][r] - f[i][l - 1]*p[r - l + 1] + 1LL*MOD*MOD)%MOD;
  16.     return res;
  17. }
  18.  
  19. int main(){
  20.     ios_base::sync_with_stdio(0);
  21.     cin.tie(0);
  22.     cin>>n>>q;
  23.     p[0] = 1;
  24.     for(int i=1;i<=M;i++){
  25.         p[i] = p[i - 1]*base%MOD;
  26.     }
  27.     for(int i=1;i<=n;i++){
  28.         string s;
  29.         cin>>s;
  30.         int len = s.size();
  31.         s = ' ' + s;
  32.         for(int j=1;j<=len;j++){
  33.             f[i][j] = (f[i][j - 1]*base + s[j] - 'a' + 1)%MOD;
  34.         }
  35.         b[i] = len;
  36.     }
  37.     for(int i=1;i<=q;i++){
  38.         string s;
  39.         cin>>s;
  40.         if(s.size() == 1 and s[0] == '*'){
  41.             cout<<n<<"\n";
  42.             continue;
  43.         }
  44.         int len = s.size();
  45.         s = ' ' + s;
  46.         int xx;
  47.         for(int j=1;j<=len;j++){
  48.             if(s[j] == '*')xx = j;
  49.         }
  50.         ll Hash1 = 0, Hash2 = 0;
  51.         for(int j=1;j<=xx-1;j++){
  52.             Hash1 = (Hash1*base + s[j] - 'a' + 1)%MOD;
  53.         }
  54.         for(int j=xx+1;j<=len;j++){
  55.             Hash2 = (Hash2*base + s[j] - 'a' + 1)%MOD;
  56.         }
  57.         ll ans = 0;
  58.         for(int j=1;j<=n;j++){
  59.             if(b[j] + 1 < len)continue;
  60.             if(xx == 1){
  61.                 if(Hash2 == get(b[j] - len + xx + 1, b[j], j))ans++;
  62.             }
  63.             else if(xx == len){
  64.                 if(Hash1 == get(1, xx - 1, j))ans++;
  65.             }
  66.             else {
  67.                 if(Hash1 == get(1, xx - 1, j) and Hash2 == get(b[j] - len + xx + 1, b[j], j))ans++;
  68.             }
  69.         }
  70.         cout<<ans<<"\n";
  71.     }
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/02gccd
language:
C++14 (gcc 8.3)
created:
7 days 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!