Submission #638518

#	Time	Username	Problem	Language	Result	Execution time	Memory
638518		NintsiChkhaidze	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	701 ms	42408 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define s second
#define pb push_back
#define f first
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r

#define int ll
using namespace std;
 
const int N = 5005,mod = 1000000007;
int len[N],h[N][N],p[N];

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,m;
    cin>>n>>m;

    p[0] = 1;
    for (int i = 1; i <= 5000; i++)
        p[i] = (p[i - 1]*31)%mod;

    for (int i = 1; i <= n; i++){
        string s;
        cin>>s;
        
        len[i] = s.size();
        for (int j = 0; j < len[i]; j++){
            if(j) h[i][j] = (h[i][j - 1] + (p[j]*(s[j] - 'A' + 1))%mod)%mod;
            else h[i][j] = (s[j] - 'A' + 1);
        }
    }

    while(m--){
        string a,b;
        cin>>a>>b;
        int cnt=0,A = a.size(),B = b.size(),ha = 0,hb = 0;
        for (int i = 0; i < A; i++) ha = (ha + (p[i]*(a[i] - 'A' + 1)))%mod;
        for (int i = 0; i < B; i++) hb = (hb + (p[i]*(b[i] - 'A' + 1)))%mod;
        
        for (int i = 1; i <= n; i++){
            int Ha = h[i][A - 1];
            if (Ha != ha) continue;
            int Hb = ((h[i][len[i] - 1] - h[i][len[i] - B - 1])%mod + mod)%mod;
            if (Hb == (hb*p[len[i] - B])%mod) cnt++;
        }

        cout<<cnt<<"\n";
    }
}

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