//dau tuyen
//dau tuyen
//dau tuyen
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "rna"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7,nmax=1e5+5,nmax2=2e6+5,can=1400,base=31;
string a[nmax];
pair<string,string> qu[nmax];
vector<ll> hash1[nmax];
ll hash2[nmax];
ll hash3[nmax];
ll P[nmax2];
int trie[can+5][5];
int trie2[can*5+5][can+5][5];
int sl[can*5+5][can*5+5];
int id=0,id2[can*5+5];
void build(string s1,string s2)
{
int p=0,p2=0;
for(int i=1;i<s1.size();i++)
{
int ch=s1[i]-'A';
if(!trie[p][ch]) trie[p][ch]=++id;
p=trie[p][ch];
}
reverse(s2.begin(),s2.end());
for(int i=0;i<s2.size()-1;i++)
{
int ch=s2[i]-'A';
if(!trie2[p][p2][ch]) trie2[p][p2][ch]=++id2[p];
p2=trie2[p][p2][ch];
sl[p][p2]+=1;
}
}
int get(string s1,string s2)
{
int p=0,p2=0;
for(int i=1;i<s1.size();i++)
{
int ch=s1[i]-'A';
if(!trie[p][ch]) return 0;
p=trie[p][ch];
}
for(int i=0;i<s2.size()-1;i++)
{
int ch=s2[i]-'A';
if(!trie2[p][p2][ch]) return 0;
p2=trie2[p][p2][ch];
}
return sl[p][p2];
}
ll gethash(int idx,int l,int r)
{
return ((hash1[idx][r]-hash1[idx][l-1]*P[r-l+1])+MOD*MOD)%MOD;
}
vector<int> grt,sml;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,t;
cin>>n>>t;
for(int i=1;i<=n;i++)
{
cin>>a[i];
for(auto &i:a[i])
{
if(i=='G') i='B';
if(i=='U') i='D';
}
if(a[i].size()>can) grt.push_back(i);
else sml.push_back(i);
}
for(int i=1;i<=t;i++)
{
cin>>qu[i].fi>>qu[i].se;
for(auto &i:qu[i].fi)
{
if(i=='G') i='B';
if(i=='U') i='D';
}
for(auto &i:qu[i].se)
{
if(i=='G') i='B';
if(i=='U') i='D';
}
}
P[0]=1;
for(int i=1;i<=2000000;i++) P[i]=(P[i-1]*base)%MOD;
for(int i=1;i<=n;i++)
{
a[i]=" "+a[i];
hash1[i].resize(a[i].size());
for(int j=1;j<a[i].size();j++)
{
hash1[i][j]=(hash1[i][j-1]*base+a[i][j]-'A'+1)%MOD;
}
}
for(int i=1;i<=t;i++)
{
qu[i].fi=" "+qu[i].fi;
qu[i].se=" "+qu[i].se;
for(int j=1;j<qu[i].fi.size();j++)
{
hash2[i]=(hash2[i]*base+qu[i].fi[j]-'A'+1)%MOD;
}
for(int j=1;j<qu[i].se.size();j++)
{
hash3[i]=(hash3[i]*base+qu[i].se[j]-'A'+1)%MOD;
}
}
for(auto i:sml)
{
string s=" ";
for(int j=1;j<a[i].size();j++)
{
s+=a[i][j];
build(s,a[i]);
}
}
for(int i=1;i<=t;i++)
{
int ans=0;
for(auto j:grt)
{
if(gethash(j,1,qu[i].fi.size()-1)==hash2[i] and
gethash(j,a[j].size()-qu[i].se.size()+1,a[j].size()-1)==hash3[i])
{
ans++;
}
}
if(qu[i].fi.size()<can and qu[i].se.size()<can)
{
reverse(qu[i].se.begin(),qu[i].se.end());
ans+=get(qu[i].fi,qu[i].se);
}
cout<<ans<<endl;
}
}
/*
*/
Compilation message
selling_rna.cpp:12: warning: "task" redefined
12 | #define task "rna"
|
selling_rna.cpp:11: note: this is the location of the previous definition
11 | #define task "task"
|
selling_rna.cpp: In function 'void build(std::string, std::string)':
selling_rna.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i=1;i<s1.size();i++)
| ~^~~~~~~~~~
selling_rna.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0;i<s2.size()-1;i++)
| ~^~~~~~~~~~~~
selling_rna.cpp: In function 'int get(std::string, std::string)':
selling_rna.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=1;i<s1.size();i++)
| ~^~~~~~~~~~
selling_rna.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0;i<s2.size()-1;i++)
| ~^~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int j=1;j<a[i].size();j++)
| ~^~~~~~~~~~~~
selling_rna.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int j=1;j<qu[i].fi.size();j++)
| ~^~~~~~~~~~~~~~~~
selling_rna.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int j=1;j<qu[i].se.size();j++)
| ~^~~~~~~~~~~~~~~~
selling_rna.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int j=1;j<a[i].size();j++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
34832 KB |
Output is correct |
| 2 |
Correct |
14 ms |
34652 KB |
Output is correct |
| 3 |
Correct |
14 ms |
34908 KB |
Output is correct |
| 4 |
Correct |
13 ms |
34652 KB |
Output is correct |
| 5 |
Correct |
14 ms |
34648 KB |
Output is correct |
| 6 |
Correct |
14 ms |
34652 KB |
Output is correct |
| 7 |
Correct |
13 ms |
34652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
271 ms |
257876 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
32360 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
58372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
34832 KB |
Output is correct |
| 2 |
Correct |
14 ms |
34652 KB |
Output is correct |
| 3 |
Correct |
14 ms |
34908 KB |
Output is correct |
| 4 |
Correct |
13 ms |
34652 KB |
Output is correct |
| 5 |
Correct |
14 ms |
34648 KB |
Output is correct |
| 6 |
Correct |
14 ms |
34652 KB |
Output is correct |
| 7 |
Correct |
13 ms |
34652 KB |
Output is correct |
| 8 |
Runtime error |
271 ms |
257876 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
