// In the name of god
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Sort(x) sort(all(x))
#define debug(x) cerr << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;
const ll maxn = 1e5 + 6, inf = 1e18, mod = 1e9 + 7, mod2 = 1e9 + 9;
ll n, m, pw26[2][maxn];
str s[maxn], t[maxn];
vector <int> v[2][maxn];
void hAsh(int k){
int sz = s[k].size();
for(int i = 0; i < sz; i ++){
ll c = s[k][i] - 'A';
v[0][k].pb(c * pw26[0][i] % mod);
v[1][k].pb(c * pw26[1][i] % mod2);
if(i > 0)(v[0][k][i] += v[0][k][i - 1]) %= mod;
if(i > 0)(v[1][k][i] += v[1][k][i - 1]) %= mod2;
}
}
pll HASH(int k){
int sz = t[k].size();
ll x = 0, x2 = 0;
for(int i = 0; i < sz; i ++){
ll c = t[k][i] - 'A';
(x += c * pw26[0][i] % mod) %= mod;
(x2 += c * pw26[1][i] % mod2) %= mod2;
}
pll pr = {x, x2};
return pr;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
pw26[0][0] = 1;
pw26[1][0] = 1;
ll z = 26;
for(int i = 1; i < maxn; i ++){
pw26[0][i] = (pw26[0][i - 1] * z % mod);
pw26[1][i] = (pw26[1][i - 1] * z % mod2);
}
cin >> n >> m;
for(int i = 0; i < n; i ++){
cin >> s[i];
hAsh(i);
}
for(int i = 0; i < m; i ++){
cin >> t[i * 2] >> t[i * 2 + 1];
pll p1 = HASH(i * 2);
pll p2 = HASH(i * 2 + 1);
ll ans = 0;
for(int j = 0; j < n; j ++){
if(s[j].size() < t[i * 2].size())continue;
if(s[j].size() < t[i * 2 + 1].size())continue;
if(v[0][j][t[i * 2].size() - 1] != p1.F)continue;
if(v[1][j][t[i * 2].size() - 1] != p1.S)continue;
ll x = v[0][j][s[j].size() - 1];
int szj = s[j].size();
int szq = t[i * 2 + 1].size();
int dif = szj;
dif -= szq;
if(dif)x = (x - v[0][j][dif - 1] + mod) % mod;
if((p2.F * pw26[0][dif] % mod) != x)continue;
x = v[1][j][s[j].size() - 1];
if(dif)x = (x - v[1][j][dif - 1] + mod2) % mod2;
if((p2.S * pw26[1][dif] % mod2) != x)continue;
ans ++;
}
cout << ans << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12908 KB |
Output is correct |
2 |
Correct |
10 ms |
12908 KB |
Output is correct |
3 |
Correct |
9 ms |
12908 KB |
Output is correct |
4 |
Correct |
10 ms |
12908 KB |
Output is correct |
5 |
Correct |
9 ms |
12908 KB |
Output is correct |
6 |
Correct |
9 ms |
12908 KB |
Output is correct |
7 |
Correct |
9 ms |
12908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
38252 KB |
Output is correct |
2 |
Correct |
809 ms |
40556 KB |
Output is correct |
3 |
Correct |
307 ms |
40044 KB |
Output is correct |
4 |
Correct |
380 ms |
40428 KB |
Output is correct |
5 |
Correct |
419 ms |
29548 KB |
Output is correct |
6 |
Correct |
328 ms |
29676 KB |
Output is correct |
7 |
Correct |
545 ms |
36332 KB |
Output is correct |
8 |
Correct |
399 ms |
40044 KB |
Output is correct |
9 |
Correct |
376 ms |
39924 KB |
Output is correct |
10 |
Correct |
1139 ms |
37688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1569 ms |
16108 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12908 KB |
Output is correct |
2 |
Correct |
10 ms |
12908 KB |
Output is correct |
3 |
Correct |
9 ms |
12908 KB |
Output is correct |
4 |
Correct |
10 ms |
12908 KB |
Output is correct |
5 |
Correct |
9 ms |
12908 KB |
Output is correct |
6 |
Correct |
9 ms |
12908 KB |
Output is correct |
7 |
Correct |
9 ms |
12908 KB |
Output is correct |
8 |
Correct |
203 ms |
38252 KB |
Output is correct |
9 |
Correct |
809 ms |
40556 KB |
Output is correct |
10 |
Correct |
307 ms |
40044 KB |
Output is correct |
11 |
Correct |
380 ms |
40428 KB |
Output is correct |
12 |
Correct |
419 ms |
29548 KB |
Output is correct |
13 |
Correct |
328 ms |
29676 KB |
Output is correct |
14 |
Correct |
545 ms |
36332 KB |
Output is correct |
15 |
Correct |
399 ms |
40044 KB |
Output is correct |
16 |
Correct |
376 ms |
39924 KB |
Output is correct |
17 |
Correct |
1139 ms |
37688 KB |
Output is correct |
18 |
Execution timed out |
1569 ms |
16108 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |