Submission #882091

#	Time	Username	Problem	Language	Result	Execution time	Memory
882091		DucNguyen2007	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	147 ms	2652 KiB

necklace

#include<bits/stdc++.h>
using namespace std;
const int maxN=1e6+5;
#define ll long long
#define ben(x) x.begin(),x.end()
string s,t;
ll ans[3],n,m,p1[maxN+1],p2[maxN+1];
void calc(string s,ll p[])
{
    ll n=s.length();
    p[0]=0;
    for(int i=1;i<n;i++)
    {

        ll j=p[i-1];
        while(j>0&&s[i]!=s[j])
        {
            j=p[j-1];
        }
        if(s[i]==s[j])
        {
            j++;
        }
        p[i]=j;
    }
}
void solve(string s,string t,bool rev)
{
    string t_rev=t;
    reverse(ben(t_rev));
    for(int i=0;i<n;i++)
    {
        string l=s.substr(0,i),r=s.substr(i,n);
        reverse(ben(l));
        string a=l+"#"+t;
        string b=r+"#"+t_rev;
        calc(a,p1);
        calc(b,p2);
        for(int j=1;j<=m;j++)
        {
            ll cur1=p1[i+j];
            ll cur2=p2[n+m-j-i];
            if(cur1+cur2>ans[0])
            {
                ans[0]=cur1+cur2;
                ans[1]=i-p1[i+j];
                if(rev)
                {
                    ans[2]=m-j-cur2;
                }
                else ans[2]=j-cur1;
            }
        }
    }
}
int main()
{
    cin>>s>>t;
    n=s.length(),m=t.length();
    solve(s,t,0);
    reverse(ben(t));
    solve(s,t,1);
    cout<<ans[0]<<'\n'<<ans[1]<<" "<<ans[2];
}

• Subtask 1: 15 / 15