#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
#define gcd __gcd
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
struct piii {
int first , second , third;
};
typedef pair<pii , pii> piiii;
const ll MAX_N = 1e5 + 20 , md = 1100000123;
ll tav(ll n , ll k){
ll res = 1;
while(k > 0){
if(k & 1){
res *= n;
}
n *= n;
k /= 2;
}
return res;
}
vector<ll> ph[MAX_N] , sh[MAX_N] , p , s;
ll oo , qq , sz[MAX_N] , x = 0 , qh[MAX_N] , oh[MAX_N] , osz[MAX_N] , qsz[MAX_N];
map<pii , int> mp[500][500];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n , m , sq;
cin>>n>>m; sq = sqrt(n);
if(n <= 5e3 || m <= 5e3){
for(int i = 0 ; i < n ; i++){
string s;
cin>>s;
ll h = s.size(); sz[i] = h;
for(int j = 0 ; j < h ; j++){
if(s[j] == 'A'){
s[j] = 0;
}
if(s[j] == 'C'){
s[j] = 1;
}
if(s[j] == 'G'){
s[j] = 2;
}
if(s[j] == 'U'){
s[j] = 3;
}
}
ll t = 1 , hash = 0;
ph[i].resize(h); sh[i].resize(h);
for(int j = 0 ; j < h ; j++){
hash += 1ll * t * s[j]; hash %= md;
t *= 4; t %= md;
ph[i][j] = hash;
}
hash = 0; t = 1;
for(int j = h - 1 ; j >= 0 ; j--){
hash += 1ll * t * s[j]; hash %= md;
t *= 4; t %= md;
sh[i][j] = hash;
}
}
for(int i = 0 ; i < m ; i++){
string o , q;
cin>>o>>q;
ll hash = 0 , t = 1 , os = o.size() , qs = q.size(); osz[i] = os; qsz[i] = qs;
for(int j = 0 ; j < os ; j++){
if(o[j] == 'A'){
o[j] = 0;
}
if(o[j] == 'C'){
o[j] = 1;
}
if(o[j] == 'G'){
o[j] = 2;
}
if(o[j] == 'U'){
o[j] = 3;
}
}
for(int j = 0 ; j < qs ; j++){
if(q[j] == 'A'){
q[j] = 0;
}
if(q[j] == 'C'){
q[j] = 1;
}
if(q[j] == 'G'){
q[j] = 2;
}
if(q[j] == 'U'){
q[j] = 3;
}
}
for(int j = 0 ; j < os ; j++){
hash += 1ll * t * o[j]; hash %= md;
t *= 4; t %= md;
}
oh[i] = hash;
hash = 0; t = 1;
for(int j = qs - 1 ; j >= 0 ; j--){
hash += 1ll * t * q[j]; hash %= md;
t *= 4; t %= md;
}
qh[i] = hash;
}
for(int i = 0 ; i < m ; i++){
ll cnt = 0;
for(int j = 0 ; j < n ; j++){
if(osz[i] > sz[j] || qsz[i] > sz[j]) continue;
if(oh[i] != ph[j][osz[i] - 1]) continue;
if(qh[i] != sh[j][sz[j] - qsz[i]]) continue;
cnt++;
}
cout<<cnt<<'\n';
}
return 0;
}
for(int i = 0 ; i < n ; i++){
string s;
cin>>s;
ll h = s.size();
if(h < sq){
for(int j = 0 ; j < h ; j++){
if(s[j] == 'A'){
s[j] = 0;
}
if(s[j] == 'C'){
s[j] = 1;
}
if(s[j] == 'G'){
s[j] = 2;
}
if(s[j] == 'U'){
s[j] = 3;
}
}
ll t = 1 , hash = 0;
p.resize(h); s.resize(h);
for(int j = 0 ; j < h ; j++){
hash += 1ll * t * s[j]; hash %= md;
t *= 4; t %= md;
p[j] = hash;
}
hash = 0; t = 1;
for(int j = h - 1 ; j >= 0 ; j--){
hash += 1ll * t * s[j]; hash %= md;
t *= 4; t %= md;
s[j] = hash;
}
for(int i = 0 ; i < h ; i++){
for(int j = 0 ; j < h ; j++){
mp[i][j][{p[i] , s[j]}]++;
}
}
continue;
}
sz[x] = h;
for(int j = 0 ; j < h ; j++){
if(s[j] == 'A'){
s[j] = 0;
}
if(s[j] == 'C'){
s[j] = 1;
}
if(s[j] == 'G'){
s[j] = 2;
}
if(s[j] == 'U'){
s[j] = 3;
}
}
ll t = 1 , hash = 0;
ph[x].resize(h); sh[x].resize(h);
for(int j = 0 ; j < h ; j++){
hash += 1ll * t * s[j]; hash %= md;
t *= 4; t %= md;
ph[x][j] = hash;
}
hash = 0; t = 1;
for(int j = h - 1 ; j >= 0 ; j--){
hash += 1ll * t * s[j]; hash %= md;
t *= 4; t %= md;
sh[x][j] = hash;
}
x++;
}
for(int i = 0 ; i < m ; i++){
string o , q;
cin>>o>>q;
ll hash = 0 , t = 1 , os = o.size() , qs = q.size(); osz[i] = os; qsz[i] = qs;
for(int j = 0 ; j < os ; j++){
if(o[j] == 'A'){
o[j] = 0;
}
if(o[j] == 'C'){
o[j] = 1;
}
if(o[j] == 'G'){
o[j] = 2;
}
if(o[j] == 'U'){
o[j] = 3;
}
}
for(int j = 0 ; j < qs ; j++){
if(q[j] == 'A'){
q[j] = 0;
}
if(q[j] == 'C'){
q[j] = 1;
}
if(q[j] == 'G'){
q[j] = 2;
}
if(q[j] == 'U'){
q[j] = 3;
}
}
for(int j = 0 ; j < os ; j++){
hash += 1ll * t * o[j]; hash %= md;
t *= 4; t %= md;
}
oo = hash;
hash = 0; t = 1;
for(int j = qs - 1 ; j >= 0 ; j--){
hash += 1ll * t * q[j]; hash %= md;
t *= 4; t %= md;
}
qq = hash;
ll ans = mp[os][qs][{oo , qq}];
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(osz[i] > sz[j] || qsz[i] > sz[j]) continue;
if(oh[i] != ph[j][osz[i] - 1]) continue;
if(qh[i] != sh[j][sz[j] - qsz[i]]) continue;
ans++;
}
cout<<ans<<'\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
11 ms |
16748 KB |
Output is correct |
| 3 |
Correct |
11 ms |
16748 KB |
Output is correct |
| 4 |
Correct |
12 ms |
16748 KB |
Output is correct |
| 5 |
Correct |
12 ms |
16748 KB |
Output is correct |
| 6 |
Correct |
11 ms |
16748 KB |
Output is correct |
| 7 |
Correct |
12 ms |
16748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
48236 KB |
Output is correct |
| 2 |
Correct |
380 ms |
48620 KB |
Output is correct |
| 3 |
Correct |
250 ms |
48492 KB |
Output is correct |
| 4 |
Correct |
315 ms |
48748 KB |
Output is correct |
| 5 |
Correct |
426 ms |
36588 KB |
Output is correct |
| 6 |
Correct |
421 ms |
36972 KB |
Output is correct |
| 7 |
Correct |
229 ms |
40556 KB |
Output is correct |
| 8 |
Correct |
383 ms |
48748 KB |
Output is correct |
| 9 |
Correct |
382 ms |
48492 KB |
Output is correct |
| 10 |
Correct |
557 ms |
48620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
33772 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
11 ms |
16748 KB |
Output is correct |
| 3 |
Correct |
11 ms |
16748 KB |
Output is correct |
| 4 |
Correct |
12 ms |
16748 KB |
Output is correct |
| 5 |
Correct |
12 ms |
16748 KB |
Output is correct |
| 6 |
Correct |
11 ms |
16748 KB |
Output is correct |
| 7 |
Correct |
12 ms |
16748 KB |
Output is correct |
| 8 |
Correct |
141 ms |
48236 KB |
Output is correct |
| 9 |
Correct |
380 ms |
48620 KB |
Output is correct |
| 10 |
Correct |
250 ms |
48492 KB |
Output is correct |
| 11 |
Correct |
315 ms |
48748 KB |
Output is correct |
| 12 |
Correct |
426 ms |
36588 KB |
Output is correct |
| 13 |
Correct |
421 ms |
36972 KB |
Output is correct |
| 14 |
Correct |
229 ms |
40556 KB |
Output is correct |
| 15 |
Correct |
383 ms |
48748 KB |
Output is correct |
| 16 |
Correct |
382 ms |
48492 KB |
Output is correct |
| 17 |
Correct |
557 ms |
48620 KB |
Output is correct |
| 18 |
Runtime error |
39 ms |
33772 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Halted |
0 ms |
0 KB |
- |
