Submission #1305836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305836		DanielPr8	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	253 ms	508 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
using ll = int;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;

#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()


void calc(string& s, vll& pi, ll ad){
    pi[ad]=0;
    for(ll j, i=ad+1; i < s.size(); ++i){
        j = pi[i-1]+ad;
        pi[i]=0;
        while(j>=ad){
            if(s[j]==s[i]){
                pi[i]=j-ad+1;
                break;
            }
            if(j==ad)break;
            j=pi[j-1]+ad;
        }
    }
}

pair<ll,pll> solve(string& s, string& t, vll& kmp1, vll& kmp2){
    string st = s+"#"+t;
    string ts = t+"#"+s;
    ll ans=0, m=t.size();
    pll ret={0,0};
    reverse(all(ts));
    for(ll i = 0; i <= s.size(); ++i){
        calc(st, kmp1, i);
        calc(ts, kmp2, s.size()-i);
        for(ll j = -1; j < m; ++j){
            ll cur = kmp1[s.size()+1+j]+kmp2[s.size()+m-j-1];
            if(cur>ans){
                ans=cur;
                ret = {i-kmp2[s.size()+m-j-1],j+1-kmp1[s.size()+1+j]};
            }
        }
    }
    return {ans,ret};
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    string s, t;
    cin >> s >> t;
    vll kmp1, kmp2;
    kmp1=kmp2=vll(s.size()+t.size()+1);
    pair<ll,pll> ans = solve(s,t,kmp1, kmp2);
    reverse(all(t));
    pair<ll,pll> ans2 = solve(s,t,kmp1, kmp2);
    if(ans.f>ans2.f){
        cout << ans.f << "\n" << ans.s.f << " " << ans.s.s;
    }
    else{
        cout << ans2.f << "\n" << ans2.s.f << " " << t.size()-ans2.s.s-ans2.f;
    }
}

• Subtask 1: 15 / 15