Submission #1305297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305297		miniyahirpro	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	355 ms	564 KiB

necklace

#include<bits/stdc++.h>
#define  S second
#define  F first
#define vll vector<ll>
#define mll vector<vll>
#define vi vector<int>
#define mi vector<vi>
#define all(a) (a).begin(),(a).end()
#define rep(i,x,y) for(int i=x; i<y;i++)
#define rrep(i,x,y) for(int i=x; i>=y;i--)
#define endl "\n"
using namespace std;
typedef short int ll;

vector<ll> f(string s1, string s2){
    int n=s1.size(), m=s2.size();
    vector<ll> ans(3);
    rep(inicio,0,n){
        string aux=s1.substr(inicio);
        // cout <<"original " << s1 << endl;
        // cout <<"para el " << aux << " " << " con " << s2 << endl; 
        string s=aux+"#"+s2;
        int tam=s.size();
        vll kmp(tam);
        vll sufijo(m);
        rep(i,1,tam){
            int j=kmp[i-1];
            while(j && s[i]!=s[j])
                j=kmp[j-1];
            kmp[i]=j+(s[i]==s[j]);

            if(i>=(int)aux.size()+1)
                sufijo[i-(int)aux.size()-1ll]=kmp[i];
        }

        vll prefijo(m+1);
        
        aux=s1.substr(0,inicio);
        reverse(all(aux));
        string aux2=s2;
        reverse(all(aux2));
        s=aux+"#"+aux2;
        tam=s.size();
        kmp.assign(tam,0);

        rep(i,1,tam){
            int j=kmp[i-1];
            while(j && s[i]!=s[j])
                j=kmp[j-1];
            kmp[i]=j+(s[i]==s[j]);

            if(i>=(int)aux.size()+1)
                prefijo[m-1-(i-(int)aux.size()-1ll)]=kmp[i];
        }
        // cout <<"sufijos" << endl;
        // for(auto &it: sufijo) cout << it  << " ";
        // cout << endl;
        // cout <<"prefijos" << endl;
        // for(auto &it: prefijo) cout << it  << " ";
        // cout << endl;
        rep(i,0,m) if(sufijo[i]+prefijo[i+1]>ans[0]){
            ans[0]=sufijo[i]+prefijo[i+1];
            ans[1]=inicio-prefijo[i+1];
            ans[2]=i-sufijo[i]+1;
        }
        
    }

    return ans;
}
void solve(){
    string s, t; cin >> s >> t;
    int m=t.size();

    vector<ll> ans1=f(s, t);

    reverse(all(t));
    vector<ll> ans2=f(s,t);

    if(ans1[0]<ans2[0]){
        ans1=ans2;
        ans1[2]=m-1-ans1[2];
        ans1[2]=ans1[2]-ans1[0]+1;
    }

    cout << ans1[0] << endl;
    cout << ans1[1] << " " << ans1[2] << endl;
    

}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    solve();
  
}

• Subtask 1: 15 / 15