Buzzwords

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;

const int A = 911382323;
const int B = 972663749;
const int N = 1e5;
string S[N];
int H[N], L[N], P[N];

vi hh(const string& a) {
  vi h(sz(a));
  h[0] = a[0];
  rep(i,1,sz(a)) {
    h[i] = (h[i-1]*ll(A) + a[i]) % B;
  }
  return h;
}

int hget(const vi& h, int a, int b) {
  if (a == 0) return h[b];
  int r = (h[b] - h[a-1]*ll(P[b-a+1])) % B;
  return r < 0 ? r + B : r;
}

int main() {
  P[0] = 1;
  rep(i,1,N) P[i] = ll(A) * P[i-1] % B;
  string s, s0;
  getline(cin,s);
  string sq;
  getline(cin,sq);
  int q = stoi(sq);
  vi hs = hh(s);
  rep(i,0,q) {
    getline(cin,s0);
    ll hhh = s0[0];
    rep(j,1,sz(s0)) {
      hhh = (hhh*ll(A) + s0[j]) % B;
    }
    H[i] = hhh;
    L[i] = sz(s0);
  }
  int ans = 0;
  rep(i,0,sz(s)) {
    rep(j,0,q) {
      if (L[j] <= i+1 && H[j] == hget(hs,i+1-L[j],i)) {
        ++ans;
      }
    }
  }
  cout << ans << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED