# TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

80.0% (20/25)

35.8% (24/67)

# Description

#include <bits/stdc++.h>
#define int long long

using namespace std;

int M = 998244353;
int x = 137;

int h[10005], xp[10005];

void Hash(string& s) {
h[s.length()] = 0;
for(int i = s.length()-1 ; i >= 0 ; i--) {
h[i] = (h[i+1]*x%M + s[i]-'a'+1)%M;
}
}

int gethashvalue(int L, int len) {
return (h[L] - h[L+len]*xp[len]%M + M)%M;
}

int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
xp[0] = 1;
for(int i = 1 ; i < 10005 ; i++) xp[i] = xp[i-1]*x%M;

int t, q; cin >> t;
while(t--) {
string s, p; cin >> s;
Hash(s);
cin >> q;
while(q--) {
cin >> p;
int ph = 0;
for(int i = p.length()-1 ; i >= 0 ; i--) {
ph = (ph*x%M + p[i]-'a'+1)%M;
}
int cnt = 0;
for(int i = 0 ; i+p.length()-1 < s.length() ; i++) {
if(gethashvalue(i, p.length()) == ph) cnt++;
}
cout << cnt << '\n';
}
}
}


# Input Format

$T$、$P$ 都是由小寫字母所組成，長度不會超過 $10000$。

2
abcdefefef
3
bcd
ef
efef
ccodegeass
2
akira
cc

1
3
2
0
1

TIOJ 1306