Submission #1305745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305745		rodriii	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	204 ms	596 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int MXN = 500005;

vector<int> prefix_function(string s){
    //cout << s << "\n";
    int n = s.size();
    vector<int> pi(n);
    for(int i = 1; i < n; ++i){
        int j = pi[i-1];
        while(j > 0 && s[j] != s[i]){
            j = pi[j-1];
        }
        if(s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int ans = 0, ini_a, ini_b;
string s, t, revt;

vector<int> left_part(string &leftS){
    reverse(leftS.begin(), leftS.end());
    vector<int> kmp = prefix_function(leftS + '?' + revt);
    reverse(kmp.begin() + (int)leftS.size() + 1, kmp.end());
    return kmp;
}

vector<int> right_part(string &rightS){
    vector<int> kmp = prefix_function(rightS + '?' + t);
    return kmp;
}

void process(bool invertido){
    for(int i = 0; i < s.size(); ++i){
        string leftS = s.substr(0, i + 1);
        string rightS = s.substr(i + 1);
        //cout << leftS << " " << rightS << "\n";
        vector<int> a = left_part(leftS), b = right_part(rightS);
        a.emplace_back(0);
        int j = leftS.size() + 1, k = rightS.size() + 1;
        for(int r = 0; r < t.size(); ++r){
            //cout << r << " " << a[j] << " " << b[k] << "\n";
            int len = a[j + 1] + b[k];
            if(len > ans){
                ans = len;
                ini_a = i - a[j + 1] + 1;
                if(invertido) ini_b = t.size() - 1 - r - b[k];
                else ini_b = r - b[k];
            }
            j++; k++;
        }
    }
}

void solve(){
    cin >> s >> t;
    revt = t;
    reverse(t.begin(), t.end());
    swap(t, revt);
    //cout << t << " " << revt << "\n";
    process(false);
    swap(revt, t);
    process(true);
    //process();
    cout << ans << "\n";
    cout << ini_a << " " << ini_b << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) solve();
    return 0;
}

• Subtask 1: 0 / 15