Submission #1318448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318448		a.pendov	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	1 ms	588 KiB

necklace

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4099;
long long pi1[MAXN],pi2[MAXN];
long long ans=0,ansP1,ansP2,M,N;
string a,b,currStr;


signed main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>a>>b;
    N=a.size();
    M=b.size();

    for(int i=0;i<M;i++)
    {
        currStr="";
        for(int j=i;j<M;j++)currStr.push_back(b[j]);
        currStr+="#"+a+"&";
        for(int j=0;j<i;j++)currStr.push_back(b[j]);
        memset(pi1,0,sizeof(pi1));
        memset(pi2,0,sizeof(pi2));

        int curr=0;
        for(int j=1;j<N+M+2;j++)
        {
            while(curr>0&&currStr[j]!=currStr[curr])curr=pi1[curr-1];
            if(currStr[j]==currStr[curr])curr++;
            pi1[j]=curr;
        }

        reverse(currStr.begin(),currStr.end());

        for(int j=1;j<N+M+2;j++)
        {
            while(curr>0&&currStr[j]!=currStr[curr])curr=pi2[curr-1];
            if(currStr[j]==currStr[curr])curr++;
            pi2[j]=curr;
        }

        for(int j=i;j<=i+N;j++)
        {
            if(pi1[j]+pi2[M+N-j]>ans)
            {
                ans=pi1[j]+pi2[M+N-j];
                ansP1=j-i-pi2[M+N-j];
                ansP2=i-pi1[j];
            }
        }
    }

    reverse(b.begin(),b.end());

        for(int i=0;i<M;i++)
    {
        currStr="";
        for(int j=i;j<M;j++)currStr.push_back(b[j]);
        currStr+="#"+a+"&";
        for(int j=0;j<i;j++)currStr.push_back(b[j]);
        memset(pi1,0,sizeof(pi1));
        memset(pi2,0,sizeof(pi2));

        int curr=0;
        for(int j=1;j<N+M+2;j++)
        {
            while(curr>0&&currStr[j]!=currStr[curr])curr=pi1[curr-1];
            if(currStr[j]==currStr[curr])curr++;
            pi1[j]=curr;
        }

        reverse(currStr.begin(),currStr.end());

        for(int j=1;j<N+M+2;j++)
        {
            while(curr>0&&currStr[j]!=currStr[curr])curr=pi2[curr-1];
            if(currStr[j]==currStr[curr])curr++;
            pi2[j]=curr;
        }

        for(int j=i;j<=i+N;j++)
        {
            if(pi1[j]+pi2[M+N-j]>ans)
            {
                ans=pi1[j]+pi2[M+N-j];
                ansP1=j-i-pi2[M+N-j];
                ansP2=M-(i-pi1[j])-ans;
            }
        }
    }


    cout<<ans<<endl<<ansP1<<" "<<ansP2<<endl;

    return 0;
}

• Subtask 1: 0 / 15