Submission #1334739

#TimeUsernameProblemLanguageResultExecution timeMemory
1334739thanhbinh13Necklace (Subtask 4) (BOI19_necklace4)C++20
15 / 15
208 ms648 KiB
#include<bits/stdc++.h>
using namespace std;

const int N = 5e5+5;
long long p1[N],p2[N];
void fillP(string s,long long *p){
    for (int i= 1; i < s.length(); i++) {
        long long j = p[i-1];
        while(j > 0 && s[i] != s[j]) j = p[j-1];
        if (s[i] == s[j]) j++;
        p[i] = j;
    }
}
tuple<long long,long long,long long> solve(string s,string t,bool rev) {
    long long n = s.length(),m = t.length();
    tuple<long long,long long,long long> ans = {0,0,0};
    for (int i = 0; i < n; i++) {
        string s1 = s.substr(0,i),s2 = s.substr(i,n-i);
        reverse(s1.begin(),s1.end());
        string t1 = t,t2 = t;
        reverse(t2.begin(),t2.end());
        fillP(s1+'#'+t1,p1);fillP(s2+'#'+t2,p2);
        for (int j = 1; j <= m; j++ ){
            ans = max(ans,{p1[i+j]+p2[n+m-i-j],i-p1[i+j],(rev ? m-j-p2[n+m-i-j]:j-p1[i+j])});
        }
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s,t;
    cin >> s >> t;
    tuple<long long,long long,long long> ans = solve(s,t,false);
    reverse(t.begin(),t.end());
    ans = max(ans,solve(s,t,true));
    cout << get<0>(ans) << "\n" << get<1>(ans) << " "<< get<2>(ans);
}
#Verdict Execution timeMemoryGrader output
Fetching results...