#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
const int MOD1 = 1e9+7;
const int MOD2 = 998244353;
pii make_hash(string s){
int n = s.size();
int z1 = 5;
int z2 = 5;
pii hb = {0,0};
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 2;
if(b[i] > a[i])return 0; //a is smaller
if(a[i] > b[i])return 2; //a is bigger
}
return 1;
}
vector<int>sa(string s){
s+="`";
int n = s.size();
vector<int>p(n),c(n),cnt(27);
for(int i=0;i<n;i++)cnt[s[i]-'`']++;
for(int i=1;i<=26;i++)cnt[i]+=cnt[i-1];
for(int i=0;i<n;i++)p[--cnt[s[i]-'`']] = i;
c[p[0]] = 0;
int cas = 1;
for(int i=1;i<n;i++){
if(s[p[i]] != s[p[i-1]])cas++;
c[p[i]] = cas-1;
}
vector<int>pn(n),cn(n);
for(int k=0;(1<<k)<n;k++){
//we want to sort by pairs of class {x,y}
for(int i=0;i<n;i++){ //this auto sorts it by y first
pn[i] = p[i] - (1<<k);
if(pn[i] <0)pn[i]+=n;
}
cnt.assign(cas,0);
for(int i=0;i<n;i++)cnt[c[i]]++;
for(int i=1;i<cas;i++)cnt[i]+=cnt[i-1];
//counting sort /stable sort on first coord
for(int i=n-1;i>=0;i--){
p[--cnt[c[pn[i]]]] = pn[i];
}
cn[p[0]] = 0;
cas = 1;
for(int i=1;i<n;i++){
pii a = {c[p[i-1]] , c[(p[i-1] + (1<<k))%n]};
pii b = {c[p[i]] , c[(p[i] + (1<<k))%n]};
if(a != b)cas++;
cn[p[i]] = cas-1;
}
swap(cn,c);
}
return p;
}
int has[2000001];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m;
cin>>n>>m;
vector<string>s(n);
for(int i=0;i<n;i++){
cin>>s[i];
for(char &x:s[i])x+='a'-'A';
}
string f;
for(int i=0;i<n;i++){
has[f.size()] = i+1;
f+=s[i];
f+="`";
}
vector<int>sorted = sa(f);
vector<int>id;
for(int x:sorted){
if(has[x])id.push_back(has[x]-1);
}
vector<string>tmp(n);
for(int i=0;i<n;i++)tmp[i] = s[id[i]];
swap(tmp,s);
vector<vector<pii>>sh(n);
for(int i=0;i<n;i++){
int k = s[i].size();
sh[i].resize(k);
int z1 = 5;
int z2 = 5;
pii 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;
}
}
while(m--){
string p,q;
cin>>p>>q;
for(char &x:p)x+='a'-'A';
for(char &x:q)x+='a'-'A';
reverse(q.begin(),q.end());
pii suf = make_hash(q);
int ans = 0;
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;
if(R>=L){
int b = q.length();
for(int i=L;i<=R;i++)if(sh[i][b-1] == suf)ans++;
}
cout<<ans<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1549 ms |
54220 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1142 ms |
8556 KB |
Output is correct |
| 2 |
Correct |
521 ms |
5980 KB |
Output is correct |
| 3 |
Correct |
737 ms |
7284 KB |
Output is correct |
| 4 |
Correct |
323 ms |
6184 KB |
Output is correct |
| 5 |
Correct |
220 ms |
5956 KB |
Output is correct |
| 6 |
Correct |
302 ms |
7376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Execution timed out |
1549 ms |
54220 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
