# TopCoder

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

64.7% (11/17)

13.2% (15/114)

# 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

# Problem Source

TIOJ 1306

No. Testdata Range Score
1 0~9 100

# Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 5000 65536 262144 1
8 5000 65536 262144 1
9 5000 65536 262144 1