#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
using lli = long long;
const int maxN = 1e5 + 5;
const int maxS = 2e6 + 5;
const int maxA = 4;
int tr[maxS][maxA],cnt,h[maxS];
string q[maxN],s[maxN],p[maxN],s1[maxN];
int n,m,idn[maxN],idm[maxN],res[maxN];
inline k(char c)
{
if (c == 'G') return 0;
if (c == 'U') return 1;
if (c == 'C') return 2;
if (c == 'A') return 3;
}
void add(string s)
{
int node = 0;
for (char c : s)
{
if (tr[node][k(c)] == 0) tr[node][k(c)] = ++cnt;
node = tr[node][k(c)];
h[node]++;
}
}
void del(const string& s)
{
int node = 0;
for (char c : s)
{
int pos = node;
node = tr[node][k(c)];
h[node]--;
if (h[node] == 0) tr[pos][k(c)] = 0;
}
}
int calc(const string& s)
{
int node = 0;
for (char c : s)
{
if (tr[node][k(c)] == 0) return 0;
node = tr[node][k(c)];
}
return h[node];
}
bool cmp(const int& a,const int& b)
{
return s[a] < s[b];
}
bool cmp1(const int& a,const int& b)
{
return p[a] < p[b];
}
void input()
{
cnt = 0;
cin >> n >> m;
for (int i = 1;i <= n;++i)
{
cin >> s[i];
idn[i] = i;
}
for (int i = 1;i <= m;++i)
{
idm[i] = i;
cin >> p[i] >> q[i];
reverse(q[i].begin(),q[i].end());
}
sort(idn + 1,idn + n + 1,cmp);
sort(idm + 1,idm + m + 1,cmp1);
}
bool check(const string& b,const string& a)
{
if (a.size() > b.size()) return false;
for (int i = 0;i < a.size();++i)
if (a[i] != b[i]) return false;
return true;
}
void solve()
{
for (int i = 1;i <= n;++i)
{
reverse(s[i].begin(),s[i].end());
s1[i] = s[i];
reverse(s[i].begin(),s[i].end());
}
int l = 1,r = 0;
for (int i = 1;i <= m;++i)
{
while (l <= n && p[idm[i]] > s[idn[l]] && !check(s[idn[l]],p[idm[i]]))
{
if (l <= r) del(s1[idn[l]]);
++l;
}
r = max(l - 1,r);
while (r + 1 <= n && check(s[idn[r + 1]],p[idm[i]]))
{
++r;
add(s1[idn[r]]);
}
while (r >= l && !check(s[idn[r]],p[idm[i]]))
{
del(s1[idn[r]]);
--r;
}
res[idm[i]] = calc(q[idm[i]]);
}
for (int i = 1;i <= m;++i) cout << res[i] << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("D.inp","r",stdin);
// freopen("D.out","w",stdout);
input();
solve();
}
Compilation message
selling_rna.cpp:12:8: error: ISO C++ forbids declaration of 'k' with no type [-fpermissive]
12 | inline k(char c)
| ^
selling_rna.cpp: In function 'bool check(const string&, const string&)':
selling_rna.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0;i < a.size();++i)
| ~~^~~~~~~~~~
selling_rna.cpp: In function 'int k(char)':
selling_rna.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
18 | }
| ^
