Submission #1262493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262493		haha	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	110 ms	23112 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=5e3+5;
const int base=31;
const ll MOD=1e9+7;

int n,m;
string s[maxn];
string p,q;
vector<ll> Hs[maxn];
ll Pow[100005];

ll get(int i,int j,int k)
{
    return (Hs[k][j]-Hs[k][i-1]*Pow[j-i+1]+MOD*MOD)%MOD;
}

int main()
{
    Pow[0]=1;
    for(int i=1;i<=1e5;i++) Pow[i]=(Pow[i-1]*base)%MOD;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        int len=s[i].size();
        s[i]=" "+s[i];
        Hs[i].push_back(0);
        for(int j=1;j<=len;j++){
            Hs[i].push_back((Hs[i][j-1]*base+s[i][j]-'A'+1)%MOD);
        }
    }
    for(int i=1;i<=m;i++){
        cin>>p>>q;
        ll hp=0,hq=0;
        for(int j=0;j<p.size();j++) hp=(hp*base+p[j]-'A'+1)%MOD;
        for(int j=0;j<q.size();j++) hq=(hq*base+q[j]-'A'+1)%MOD;
        int ans=0;
        for(int j=1;j<=n;j++){
            ll pre=get(1,p.size(),j);
            ll suf=get(s[j].size()-q.size(),s[j].size()-1,j);
            if(pre==hp&&suf==hq) ans++;
        }
        cout<<ans<<'\n';
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40