Submission #460417

#	Time	Username	Problem	Language	Result	Execution time	Memory
460417		bonopo	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	296 ms	664 KiB

necklace

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=2e5+5, MOD=1e9+7, LOG=19;
pair<int,pair<int,int>> ans;
string s, t;

vector<int> lps(string k) {
    int m=k.size(), i=1, len=0;
    vector<int> ret(m+1);
    while(i<m) {
        if(k[i]==k[len]) ret[i++]=++len;
        else if(len) len=ret[len-1];
        else ret[i++]=0; }
    return ret;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>s>>t;
    for(int r=0, N=s.size(), M=t.size(); r<2; ++r) {
        for(int i=0; i<N; ++i) {
            string lft=s.substr(0, i), rvt=t, rit=s.substr(i);

            reverse(rvt.begin(), rvt.end());
            reverse(lft.begin(), lft.end());
            vector<int> lp=lps(lft+"$"+rvt), rp=lps(rit+"$"+t);

            for(int j=0; j<=M; ++j) {
                int len=rp[N-i+j]+lp[i+M-j];
                ans=max(ans, {len, {i-lp[i+M-j], (r?M-(j-rp[N-i+j]+len-1)-1:j-rp[N-i+j])}});
            }
        }

        reverse(begin(t), end(t));
    }

    cout<<ans.f<<el<<ans.s.f<<" "<<ans.s.s<<el;
}

// MM

• Subtask 1: 15 / 15