제출 #1288204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288204		LmaoLmao	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	246 ms	604 KiB

necklace

#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define name "a"
using namespace std;

using ii = pair<int,int>;
using aa = array<int,4>;
const int N=4e5+5;
const int MOD=1e9+7;

int p[6005];

int solve(string a,string b) {
    string s=a+'.'+b;
    int res=0;
    for(int i=1;i<s.size();i++) {
        int j=p[i-1];
        while(j>0 && s[i]!=s[j]) {
            j=p[j-1];
        }
        if(s[i]==s[j]) j++;
        p[i]=j;
        res=max(res,j);
    }
    return res;
}


int ans[3006];

aa lmao(string a,string b) {
    aa res={0,0,0};
    for(int i=0;i<=a.size();i++) {
        string t1=a.substr(0,i);
        string t2=b;
        reverse(t1.begin(),t1.end());
        reverse(t2.begin(),t2.end());
        solve(t1,t2);
        for(int j=0;j<t2.size();j++) {
            ans[j+1]=p[t2.size()-j-1+t1.size()];
            //if(i==5) cout << ans[j+1] << ' ' << j+1 << endl;
        }
        t1=a.substr(i,a.size()-i);
        reverse(t2.begin(),t2.end());
        solve(t1,t2);
        for(int j=0;j<t2.size();j++) {
            res=max(res,{ans[j+1]+p[j+t1.size()+1],i-ans[j+1],j-p[j+t1.size()+1]+1});
        }
        res=max(res,{ans[0],i-ans[0],0});
        for(int j=0;j<=3005;j++) {
            ans[j]=0;
            p[j]=0;
        }

    }
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    string a,b;
    cin >> a >> b;
    aa res1=lmao(a,b);
    reverse(b.begin(),b.end());
    aa res2=lmao(a,b);
    //cout << b << endl;
    if(res1[0]>=res2[0]) {
        cout << res1[0] << endl << res1[1] << ' ' << res1[2];
    }
    else {
        cout << res2[0] << endl << res2[1] << ' ' << b.size()-res2[2]-res2[0];
    }
    return 0;
}

• Subtask 1: 15 / 15