#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const int cst = 31;
int n,m;
vector<int> trie[2000005];
int mch[2000005][26];
int rez[100005];
int cnt;
int poze[2000005],timer=0;
int siz[2000005];
map<int,int> mp;
int op[100005];
vector<pair<pair<int,int>,int>> qrys[100005];
vector<int> pozs[100005];
void dfs(int nod)
{
poze[nod]=++timer;
siz[nod]=1;
for(auto adj:trie[nod])
{
dfs(adj);
siz[nod]+=siz[adj];
}
}
int v[2000005];
void solve(int suff)
{
int cntv=0;
sort(pozs[suff].begin(),pozs[suff].end());
for(auto x:qrys[suff])
{
rez[x.second] = upper_bound(pozs[suff].begin(),pozs[suff].end(),x.first.second) - lower_bound(pozs[suff].begin(),pozs[suff].end(),x.first.first);
}
}
string cit[100005];
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
string s,p,q;
for(int i=1;i<=n;i++)
{
cin>>cit[i];
s=cit[i];
int nod=0;
for(int j=0;j<s.size();j++)
{
if(mch[nod][s[j]-'A']==0)
{
cnt++;
mch[nod][s[j]-'A']=cnt;
trie[nod].push_back(cnt);
}
nod=mch[nod][s[j]-'A'];
}
}
dfs(0);
for(int i=1;i<=m;i++)
{
cin>>p>>q;
int nod=0;
bool bl=0;
for(int j=0;j<p.size();j++)
{
if(mch[nod][p[j]-'A']==0)
{
bl=1;
break;
}
nod=mch[nod][p[j]-'A'];
}
if(!bl)
{
int curaux=0,curp=1;
for(int j=q.size()-1;j>=0;j--)
{
curaux = (curaux + (1LL*curp*(q[j]-'A'+1)%MOD))%MOD;
curp=(curp*cst)%MOD;
}
///qrys[nod].push_back({curaux,i});
if(mp[curaux]==0) mp[curaux]=i;
op[i]=curaux;
qrys[mp[curaux]].push_back({{poze[nod],poze[nod]+siz[nod]-1},i});
}
}
for(int i=1;i<=n;i++)
{
s=cit[i];
int nod=0;
for(int j=0;j<s.size();j++)
{
nod=mch[nod][s[j]-'A'];
}
int curaux=0,curp=1;
for(int j=s.size()-1;j>=0;j--)
{
curaux = (curaux + (1LL*curp*(s[j]-'A'+1)%MOD))%MOD;
curp=(curp*cst)%MOD;
///suffs[nod].push_back(curaux);
if(mp[curaux]!=0) pozs[mp[curaux]].push_back(poze[nod]);
}
}
for(int i=m;i>0;i--)
{
if(mp[op[i]]==i)
{
solve(i);
}
}
for(int i=1;i<=m;i++)
cout<<rez[i]<<"\n";
return 0;
}
Compilation message
selling_rna.cpp: In function 'void solve(int)':
selling_rna.cpp:29:9: warning: unused variable 'cntv' [-Wunused-variable]
29 | int cntv=0;
| ^~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int j=0;j<s.size();j++)
| ~^~~~~~~~~
selling_rna.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int j=0;j<p.size();j++)
| ~^~~~~~~~~
selling_rna.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int j=0;j<s.size();j++)
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
59224 KB |
Output is correct |
2 |
Correct |
15 ms |
59224 KB |
Output is correct |
3 |
Correct |
15 ms |
59224 KB |
Output is correct |
4 |
Correct |
14 ms |
59404 KB |
Output is correct |
5 |
Correct |
14 ms |
59224 KB |
Output is correct |
6 |
Correct |
12 ms |
59224 KB |
Output is correct |
7 |
Correct |
13 ms |
59408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1549 ms |
139396 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
60820 KB |
Output is correct |
2 |
Correct |
39 ms |
60752 KB |
Output is correct |
3 |
Correct |
33 ms |
60752 KB |
Output is correct |
4 |
Correct |
31 ms |
60160 KB |
Output is correct |
5 |
Correct |
37 ms |
60988 KB |
Output is correct |
6 |
Correct |
37 ms |
61052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
59224 KB |
Output is correct |
2 |
Correct |
15 ms |
59224 KB |
Output is correct |
3 |
Correct |
15 ms |
59224 KB |
Output is correct |
4 |
Correct |
14 ms |
59404 KB |
Output is correct |
5 |
Correct |
14 ms |
59224 KB |
Output is correct |
6 |
Correct |
12 ms |
59224 KB |
Output is correct |
7 |
Correct |
13 ms |
59408 KB |
Output is correct |
8 |
Execution timed out |
1549 ms |
139396 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |