Submission #1206467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206467		sabino1	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	192 ms	53444 KiB

necklace

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

using ll = long long int;

vector<vector<int>> pp;

struct info{
    int tam, bs,bt;
    info(int tam_ = -1, int bs_ = -1, int bt_ = -1) : tam(tam_), bs(bs_), bt(bt_){}
    bool operator <(const info & ot)const{return tam < ot.tam;}
};

void get_p(string & s, vector<int> & p){
    p.resize(s.size());
    p[0] = 0;
    for(int i=1; i<s.size(); i++){
        int j = p[i-1];
        while(j != 0 && s[i] != s[j]) j = p[j-1];
        if(s[i] == s[j]) j++;
        p[i] = j;
    }
}

info solve(string & s, string & t){
    info ans(-1,-1,-1);
    for(int i=s.size()-1; i>=0; i--){
        // s + '#' + t
        // n1 + 1 + n2
        int n1 = s.size()-i;
        int n2 = t.size();
        // cout << s.substr(i,n1) << '#' << t << endl;
        for(int j=0; j < n2; j++){
            // s: (i) xxxxx yyyyy
            // t:     yyyyy xxxxx (j)
            // bx = begin_x, mx = mid_x (pela esquerda), ex = end_x
            int id = n1+1+j;
            if(pp[i][id] == 0) continue;
            int tam1 = pp[i][id];
            int bs = i, ms = i+tam1-1;

            int mt = j-tam1+1, et = j;
            
            int i2 = i+tam1, id2 = (j-tam1) + (s.size()-(i+tam1)) + 1;

            // cout << "opa " << i << ' ' << j <<  ' ' << tam1 << ' ' << i+tam1 << ' ' << j-tam1 << endl;
            int tam2 = ((i2 >= pp.size() || id2 < 0 || id2 >= pp[i2].size()) ? 0 : pp[i2][id2]);
            int es = i+tam1+tam2-1;
            int bt = j-tam1-tam2+1;
            // cout << "ans " << tam1+tam2 << ' ' << bs << ' ' << bt << '\n';
            ans = max(ans, info(tam1+tam2, bs, bt));
        }   
    }
    return ans;
}

void test(){
    string s,t;
    cin >> s >> t;
    pp.resize(s.size());
    for(int i=0; i<s.size(); i++){
        string str = s.substr(i,s.size()-i) + "#" + t;
        get_p(str,pp[i]);
    }
    info ans = solve(s,t);
    reverse(s.begin(), s.end());
    for(int i=0; i<s.size(); i++){
        string str = s.substr(i,s.size()-i) + "#" + t;
        get_p(str,pp[i]);
    }
    info inv = solve(s,t);
    inv.bs = abs(int(s.size())-1 - inv.bs);
    inv.bs = inv.bs-inv.tam+1;
    ans = max(ans,inv);
    cout << ans.tam << '\n';
    cout << ans.bs << ' ' << ans.bt << '\n';
}

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int ttt_ = 1;
    // cin >> ttt_;
    while(ttt_--) test();
    return 0;
}

• Subtask 1: 0 / 15