#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define BIT(x,i) ((1LL<<i)&x)
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ll long long
#define ull unsigned long long
#define name "file"
const int mod=int(1e9+7);
int pi[8]={0,0,1,-1,1,1,-1,-1};
int pj[8]={-1,1,0,0,1,-1,1,-1};
template<class A,class B> inline void add(A &a,B b) { a+=b;while (a>=mod) a-=mod;}
template<class A,class B> inline void sub(A &a,B b) { a-=b;while (a>=mod) a-=mod;while (a<0) a+=mod;}
template<class A,class B> bool _max(A &a,B b) {if (a<b) return a=b,1; return 0;}
template<class A,class B> bool _min(A &a,B b) {if (a>b) return a=b,1; return 0;}
const int nmax=5010;
unordered_map<int,unordered_map<int,ll>> prefix[nmax],suffix[nmax];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
if (fopen(name".inp","r"))
{
freopen(name".inp","r",stdin);
freopen(name".out","w+",stdout);
}
int n,m;cin>>n>>m;
const int base0=1912;
const int base1=2410;
const int mod0=19122007;
const int mod1=24102007;
for(int i=1;i<=n;i++)
{
string st,a;
cin>>st;a=st;
st=' '+st;
for(int j=1;j<st.size();j++)
{
prefix[i][j][0]=(1LL*prefix[i][j-1][0]*base0+(st[j]-'A'+1))%mod0;
//prefix[i][j][1]=(1LL*prefix[i][j-1][1]*base1+(st[j]-'A'+1))%mod1;
}
reverse(all(a));
a=' '+a;
for(int j=1;j<a.size();j++){
suffix[i][j][0]=(1LL*suffix[i][j-1][0]*base0+(a[j]-'A'+1))%mod0;
// suffix[i][j][1]=(1LL*suffix[i][j-1][1]*base1+(a[j]-'A'+1))%mod1;
}
}
for(int i=1;i<=m;i++){
string a,b;
cin>>a>>b;
ll P1=0,S1=0,P2=0,S2=0,cnt=0;
for(int j=0;j<a.size();j++)
{
P1=(1LL*P1*base0+(a[j]-'A'+1))%mod0;
// P2=(1LL*P2*base1+(a[j]-'A'+1))%mod1;
}
for(int j=b.size()-1;j>=0;j--){
S1=(1LL*S1*base0+(b[j]-'A'+1))%mod0;
// S2=(1LL*S2*base1+(b[j]-'A'+1))%mod1;
}
for(int j=1;j<=n;j++)
if (prefix[j][a.size()][0]==P1 and suffix[j][b.size()][0]==S1) cnt++;
cout<<cnt<<"\n";
}
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int j=1;j<st.size();j++)
| ~^~~~~~~~~~
selling_rna.cpp:48:26: 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 j=1;j<a.size();j++){
| ~^~~~~~~~~
selling_rna.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int j=0;j<a.size();j++)
| ~^~~~~~~~~
selling_rna.cpp:56:22: warning: unused variable 'P2' [-Wunused-variable]
56 | ll P1=0,S1=0,P2=0,S2=0,cnt=0;
| ^~
selling_rna.cpp:56:27: warning: unused variable 'S2' [-Wunused-variable]
56 | ll P1=0,S1=0,P2=0,S2=0,cnt=0;
| ^~
selling_rna.cpp:33:15: warning: unused variable 'base1' [-Wunused-variable]
33 | const int base1=2410;
| ^~~~~
selling_rna.cpp:35:15: warning: unused variable 'mod1' [-Wunused-variable]
35 | const int mod1=24102007;
| ^~~~
selling_rna.cpp:28:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:29:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | freopen(name".out","w+",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
2 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1116 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1462 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
18 ms |
17224 KB |
Execution killed with signal 8 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
2 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1116 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
1116 KB |
Output is correct |
8 |
Runtime error |
1462 ms |
1048576 KB |
Execution killed with signal 9 |
9 |
Halted |
0 ms |
0 KB |
- |