// YOU ONLY GOT ONE SHOT
#include <bits/stdc++.h>
#define put(x) cerr << #x << ": " << x << '\n'
#define line() cerr << "**************\n"
#define int long long
//#define F first
//#define S second
//#define mul(x, y) (((x) * (y)) %mod)
//#define bit(i, j) (((i)>>(j)) &1)
//#define left(id) ((id<<1) + 1)
//#define right(id) ((id<<1) + 2)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
const int maxn = 2e6 + 10, mod1 = 1e9 + 9, mod2 = 1e9 + 7, P = 737;
int n, m;
string s[maxn];
vector <int> a[maxn];
int len[maxn];
int p[2][maxn], inv[2][maxn];
vector <int> h[2][maxn];
ll mul(ll a, ll b, ll mod){
return (a * b) %mod;
}
ll power(ll a, ll b, ll mod){
ll res = 1;
for(ll i = 1, pw = a; i <= b; i <<= 1, pw = mul(pw, pw, mod))
if(b & i)
res = mul(res, pw, mod);
return res;
}
void cal(int k){
len[k] = s[k].size();
int n = len[k];
a[k].resize(n);
h[0][k].resize(n+1);
h[1][k].resize(n+1);
for(int i=0; i<n; i++)
a[k][i] = s[k][i] - 'A' + 1;
for(int i=0; i<n; i++){
h[0][k][i+1] = (h[0][k][i] + mul(a[k][i], p[0][i], mod1)) %mod1;
h[1][k][i+1] = (h[1][k][i] + mul(a[k][i], p[1][i], mod2)) %mod2;
}
}
pii get1(int n, int i){
return {h[0][i][n], h[1][i][n]};
}
pii get2(int n, int i){
int res1 = mul(h[0][i][len[i]] - h[0][i][len[i] - n], inv[0][len[i] - n], mod1);
int res2 = mul(h[1][i][len[i]] - h[1][i][len[i] - n], inv[1][len[i] - n], mod2);
return {res1, res2};
}
int solve(pii h1, pii h2, int n1, int n2){
int res = 0;
for(int i=0; i<n; i++)
if(get1(n1, i) == h1 && get2(n2, i) == h2)
res++;
return res;
}
void pre(){
p[0][0] = p[1][0] = 1;
for(int i=1; i<maxn; i++){
p[0][i] = mul(p[0][i-1], P, mod1);
p[1][i] = mul(p[1][i-1], P, mod2);
}
for(int i=0; i<maxn; i++){
inv[0][i] = power(p[0][i], mod1-2, mod1);
inv[1][i] = power(p[1][i], mod2-2, mod2);
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
pre();
cin >> n >> m;
for(int i=0; i<n; i++)
cin >> s[i], cal(i);
string pp, q;
while(m--){
cin >> pp >> q;
int n = pp.size(), n1 = pp.size(), n2 = q.size();
vector <int> b(n);
for(int i=0; i<n; i++)
b[i] = pp[i] - 'A' +1;
int Hash1[2] = {0, 0}, Hash2[2] = {0, 0};
for(int i=0; i<n; i++){
Hash1[0] = (Hash1[0] + mul(b[i], p[0][i], mod1)) %mod1;
Hash1[1] = (Hash1[1] + mul(b[i], p[1][i], mod2)) %mod2;
}
n = q.size();
b.resize(n);
for(int i=0; i<n; i++)
b[i] = q[i] - 'A' + 1;
for(int i=0; i<n; i++){
Hash2[0] = (Hash2[0] + mul(b[i], p[0][i], mod1)) %mod1;
Hash2[1] = (Hash2[1] + mul(b[i], p[1][i], mod2)) %mod2;
}
cout << solve({Hash1[0], Hash1[1]}, {Hash2[0], Hash2[1]}, n1, n2) << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
746 ms |
266464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
989 ms |
316012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1596 ms |
271820 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
746 ms |
266464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
