#include "bits/stdc++.h"
using namespace std;
#define ar array
const int N = 2e6 + 5;
const int P = 167;
const int mod = (119 << 23) + 1;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
vector<string> s(n), r(n);
vector<vector<int>> pref(n), suff(n);
for(int i=0;i<n;i++){
cin>>s[i];
} sort(s.begin(), s.end());
for(int i=0;i<n;i++){
pref[i].resize(s[i].size());
suff[i].resize(s[i].size());
r[i] = s[i];
reverse(r[i].begin(), r[i].end());
for(int j=0;j<(int)s[i].size();j++){
if(j) pref[i][j] = pref[i][j-1], suff[i][j] = suff[i][j-1];
pref[i][j] = (pref[i][j] * 1ll * P + s[i][j]) % mod;
suff[i][j] = (suff[i][j] * 1ll * P + r[i][j]) % mod;
}
}
vector<vector<ar<int, 4>>> qq(N);
vector<int> res(m);
for(int i=0;i<m;i++){
string p, q; cin>>p>>q;
reverse(q.begin(), q.end());
int h1 = 0, h2 = 0;
for(int j=0;j<(int)p.size();j++) h1 = (h1 * 1ll * P + p[j]) % mod;
for(int j=0;j<(int)q.size();j++) h2 = (h2 * 1ll * P + q[j]) % mod;
qq[(int)p.size() - 1].push_back({h1, (int)q.size() - 1, h2, i});
}
vector<ar<int, 2>> seg; seg.push_back({0, n});
vector<int> par(n, n + 1);
vector<vector<map<int, int>>> pre(n);
const int B = 10000;
for(int i=0;i<N;i++){
map<int, int> mm;
vector<ar<int, 2>> tmp;
for(auto r : seg){
int last = r[0];
while(last < r[1] && (int)s[last].size() == i) last++;
for(int j=last + 1;j<r[1];j++){
if(pref[j][i] == pref[j-1][i]) continue;
mm[pref[j-1][i]] = last;
tmp.push_back({last, j}); last = j;
} if(last < r[1]){
mm[pref[r[1] - 1][i]] = last;
tmp.push_back({last, r[1]});
}
} swap(seg, tmp);
for(auto r : seg){
if(r[1] - r[0] <= B) { par[r[0]] = r[1]; continue; }
//~ if(par[r[0]] == r[1]) continue;
par[r[0]] = r[1];
pre[r[0]].clear();
for(int j=r[0];j<r[1];j++){
if(pre[r[0]].size() < s[j].size()) pre[r[0]].resize(s[j].size());
for(int l=0;l<(int)s[j].size();l++){
pre[r[0]][l][suff[j][l]]++;
}
}
}
for(auto x : qq[i]){
if(!mm.count(x[0])) continue;
int l = mm[x[0]], r = par[l];
if(r - l <= B){
for(int j=l;j<r;j++){
if((int)s[j].size() <= x[1]) continue;
res[x[3]] += (suff[j][x[1]] == x[2]);
}
} else {
res[x[3]] = pre[l][x[1]][x[2]];
q[l].push_back({});
}
}
for(auto r : seg){
if(r[1] - r[0] <= B) continue;
for(auto x : q[r[0]]){
}
}
}
for(int i=0;i<m;i++){
cout<<res[i]<<"\n";
}
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:87:5: error: 'q' was not declared in this scope
87 | q[l].push_back({});
| ^
selling_rna.cpp:94:17: error: 'q' was not declared in this scope
94 | for(auto x : q[r[0]]){
| ^
