#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
const int MOD1 = 1e9+7;
int MOD2;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
pii make_hash(string s){
int n = s.size();
int z1 = 5;
int z2 = 5;
pii hb;
for(int i=0;i<n;i++){
int c = 1;
if(s[i] == 'C')c=2;
else if(s[i] == 'G')c=3;
else if(s[i] == 'U')c=4;
hb.fi += c * 1LL * z1%MOD1;
hb.se += c * 1LL * z2%MOD2;
if(hb.fi>=MOD1)hb.fi-=MOD1;
if(hb.se>=MOD2)hb.se-=MOD2;
z1 = z1 * 1LL * 5 %MOD1;
z2 = z2 * 1LL * 5 %MOD2;
}
return hb;
}
int cmp(string &a,string &b){
int n = a.size();
int m = b.size();
for(int i=0;i<n;i++){
if(i==m)return 1;//equal
if(b[i] > a[i])return 0; //a is smaller
if(a[i] > b[i])return 2; //a is bigger
}
return 1;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m;
cin>>n>>m;
MOD2 = uniform_int_distribution<int>(1e8,1e9)(rng);
vector<string>s(n);
for(int i=0;i<n;i++)cin>>s[i];
sort(s.begin(),s.end());
vector<vector<pii>>ph(n),sh(n); //prefix and suffix hash
for(int i=0;i<n;i++){
int k = s[i].size();
ph[i].resize(k);
sh[i].resize(k);
int z1 = 5;
int z2 = 5;
pii hb;
for(int j=0;j<k;j++){
int c = 1;
if(s[i][j] == 'C')c=2;
else if(s[i][j] == 'G')c=3;
else if(s[i][j] == 'U')c=4;
hb.fi += c * 1LL * z1%MOD1;
hb.se += c * 1LL * z2%MOD2;
if(hb.fi>=MOD1)hb.fi-=MOD1;
if(hb.se>=MOD2)hb.se-=MOD2;
z1 = z1 * 1LL * 5 %MOD1;
z2 = z2 * 1LL * 5 %MOD2;
ph[i][j] = hb;
}
z1 = 5;
z2 = 5;
hb = {0,0};
for(int j=0;j<k;j++){
int c = 1;
if(s[i][k-j-1] == 'C')c=2;
else if(s[i][k-j-1] == 'G')c=3;
else if(s[i][k-j-1] == 'U')c=4;
hb.fi += c * 1LL * z1%MOD1;
hb.se += c * 1LL * z2%MOD2;
if(hb.fi>=MOD1)hb.fi-=MOD1;
if(hb.se>=MOD2)hb.se-=MOD2;
z1 = z1 * 1LL * 5 %MOD1;
z2 = z2 * 1LL * 5 %MOD2;
sh[i][j] = hb;
}
}
//for(string x:s)cout<<x<<" ";
//cout<<'\n';
while(m--){
string p,q;
cin>>p>>q;
reverse(q.begin(),q.end());
pii pre = make_hash(p);
pii suf = make_hash(q);
int ans = 0;
int a = p.size();
int b = q.size();
//binary search for borders l and r
/*
cout<<"comps"<<'\n';
for(int i=0;i<n;i++)cout<<cmp(p,s[i])<<" ";
cout<<'\n';
*/
//this is 2222211111000000 finding a range of 11111111
int l = 0,r = n-1;
while(r>=l){
int mid = (l+r)/2;
if(cmp(p,s[mid]) <=1 )r = mid-1; //p >= s[mid];
else l=mid+1;
}//first guy >= p
int L = l;
l = 0,r = n-1;
while(r>=l){
int mid = (l+r)/2;
if(cmp(p,s[mid]) >=1)l= mid+1; //p <= s[mid]
else r=mid-1;
}
int R = r;
//last guy <= p
//cout<<L<<" "<<R<<'\n';
if(R>=L && ph[L][a-1] == pre){
for(int i=L;i<=R;i++){
if(ph[i][a-1] == pre && sh[i][b-1] == suf)ans++;
}
}
cout<<ans<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
34008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1580 ms |
7524 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
