#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];
const int segsz = 2e7;
int ndcnt = 0;
int cnt[segsz];
int ch[2][segsz];
int upd(int v,int pos,int l,int r){
int nw = ++ndcnt;
if(l==r){
cnt[nw] = cnt[v]+1;
return nw;
}
int tm = (l+r)/2;
cnt[nw] = cnt[v]+1;
if(pos<=tm){
if(!ch[0][v])ch[0][v] = ++ndcnt;
ch[1][nw] = ch[1][v];
ch[0][nw] = upd(ch[0][v],pos,l,tm);
}
else{
if(!ch[1][v])ch[1][v] = ++ndcnt;
ch[0][nw] = ch[0][v];
ch[1][nw] = upd(ch[1][v],pos,tm+1,r);
}
return nw;
}
int query(int v,int l,int r,int pos){
if(!v)return 0;
if(l==r)return cnt[v];
int tm = (l+r)/2;
if(pos<=tm)return query(ch[0][v],l,tm,pos);
else return query(ch[1][v],tm+1,r,pos);
}
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);
vector<pii>lab;
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;
lab.push_back(hb);
}
}
sort(lab.begin(),lab.end());
lab.resize(unique(lab.begin(),lab.end()) - lab.begin());
vector<int>root(n);
int prev = 0;
for(int i=0;i<n;i++){
for(pii x:sh[i]){
int y = lower_bound(lab.begin(),lab.end(),x) - lab.begin();
prev = upd(prev,y,0,lab.size()-1);
}
root[i] = prev;
}
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 y = lower_bound(lab.begin(),lab.end(),suf) - lab.begin();
if(lab[y] == suf){
ans+=query(root[R],0,lab.size()-1,y);
if(L)ans-=query(root[L-1],0,lab.size()-1,y);
}
}
cout<<ans<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1577 ms |
53172 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
13116 KB |
Output is correct |
| 2 |
Correct |
123 ms |
22124 KB |
Output is correct |
| 3 |
Correct |
133 ms |
22280 KB |
Output is correct |
| 4 |
Correct |
116 ms |
12152 KB |
Output is correct |
| 5 |
Correct |
137 ms |
19140 KB |
Output is correct |
| 6 |
Correct |
156 ms |
20036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Execution timed out |
1577 ms |
53172 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
