제출 #866813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
866813		may7002	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1354 ms	268636 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=5e3+7;
string a[N],b[N],c[N];
const int mod=1e9+7;
long long bas[N],hasa[4][N][N],hasb[4][N][N];
const int base=31;
int s=0;
long long get(int id,int vt,int l,int r)
{
    return ((hasa[id][vt][r]-hasa[id][vt][l-1]*bas[r-l+1]%mod)+1ll*mod*mod)%mod;
}
long long get1(int id,int vt,int l,int r)
{
    return ((hasb[id][vt][l]-hasa[id][vt][r+1]*bas[r-l+1]%mod)+1ll*mod*mod)%mod;
}
bool check(int i,int j)
{
    int n1=b[i].size()-1;
    int n3=a[j].size()-1;
    if(n1>n3)return 0;
    if(get(1,j,1,n1)!=get(2,i,1,n1))return 0;
    int n2=c[i].size()-1;
    if(n2>n3)return 0;
    if(get1(1,j,n3-n2+1,n3)!=get1(3,i,1,n2))return 0;
    return 1;
}
void sol1()
{
    bas[0]=1;
    for(int i=1;i<=s;i++)bas[i]=(bas[i-1]*base)%mod;
    for(int i=1;i<=n;i++)
    {
        int si=a[i].size();
        a[i]=" "+a[i];
        for(int j=1;j<=si;j++)
        {
            hasa[1][i][j]=(hasa[1][i][j-1]*base+a[i][j]-'A')%mod;
        }
        for(int j=si;j>=1;j--)
        {
            hasb[1][i][j]=(hasb[1][i][j+1]*base+a[i][j]-'A')%mod;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int si=b[i].size();
        b[i]=" "+b[i];
        for(int j=1;j<=si;j++)
        {
            hasa[2][i][j]=(hasa[2][i][j-1]*base+b[i][j]-'A')%mod;
        }
        for(int j=si;j>=1;j--)
        {
            hasb[2][i][j]=(hasb[2][i][j+1]*base+b[i][j]-'A')%mod;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int si=c[i].size();
        c[i]=" "+c[i];
        for(int j=1;j<=si;j++)
        {
            hasa[3][i][j]=(hasa[3][i][j-1]*base+c[i][j]-'A')%mod;
        }
        for(int j=si;j>=1;j--)
        {
            hasb[3][i][j]=(hasb[3][i][j+1]*base+c[i][j]-'A')%mod;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int sl=0;
        for(int j=1;j<=n;j++)
        {
            if(check(i,j))sl++;
        }
        cout<<sl<<'\n';
    }
}
int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    freopen("RNA.inp","r",stdin);
//    freopen("RNA.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            int x=a[i].size();
            s=max(s,x);
        }
    for(int i=1;i<=m;i++)
        {
            cin>>b[i]>>c[i];
            int x=b[i].size();
            int y=c[i].size();
            s=max(s,max(x,y));
        }
    sol1();
    return 0;
}
//3 3
//AA
//AA
//AGA
//AA AA
//AG GA
//AG GA

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