Submission #1175422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175422		rominanafu	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	0 / 85	1596 ms	320 KiB

necklace

#include <bits/stdc++.h>

using namespace std;

int n, m;
int pi[3005], pi_max[3005], pi_max_rev[3005], pi_pat[3005];
string a, b, b_rev;
bool rev, sw=false;

int max_len=0, ini_a, ini_b;

int encontrar(string pat) { /// encontrar una ocurrencia de pat en a

    int i,k,p=pat.size();
    pi_pat[0] = 0;

    for (i=1,k=0; i<p; i++) {
        while (k>0 && pat[i]!=pat[k])
            k = pi_pat[k-1];
        if (pat[i]==pat[k])
            k++;
        pi_pat[i] = k;
    }

    for (i=0,k=0; i<n; i++) {
        while (k>0 && pat[k]!=a[i])
            k = pi_pat[k-1];
        if (a[i]==pat[k])
            k++;
        if (k==p)
            return i-k+1;
    }

    return -1;
}

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

    cin >> a >> b;

    n = a.size(), m = b.size();
    if (m < n) {
        swap(a, b);
        swap(n, m);
        sw = true;
    }

    a = a+a;
    b_rev = b;
    reverse(b_rev.begin(), b_rev.end());

    int i, j, k;

    for(i=0; i<n; i++) {

        /// KMP para primer string
        pi[i] = 0;
        for (j=1, k=0; j<n; j++) {
            while (k>0 && a[j+i] != a[k+i])
                k = pi[k-1+i];
            if (a[j+i] == a[k+i])
                k++;
            pi[j] = k;
        }

        /// KMP para segundo string (b)
        for (j=0, k=0; j<m; j++) {
            while (k>0 && b[j] != a[k+i])
                k = pi[k-1+i];
            if (b[j] == a[k+i])
                k++;
            pi_max[j] = max(pi_max[j], k);
            if (k == n)
                k = pi[k-1+i];
        }

        /// KMP para segundo string al revés (b_rev)
        for (j=0, k=0; j<m; j++) {
            while (k>0 && b_rev[j] != a[k+i])
                k = pi[k-1+i];
            if (b_rev[j] == a[k+i])
                k++;
            pi_max_rev[j] = max(pi_max_rev[j], k);
            if (k == n)
                k = pi[k-1+i];
        }

    }

    vector<pair<int,int> > r, r_rev;
    pi_max[m] = -1, pi_max_rev[m] = -1;
    for (i=m-1; i>=0; i--) {
        if (pi_max[i] != 0 && pi_max[i] >= pi_max[i+1]) {
//            r.push_back({i-pi_max[i]+1, pi_max[i]});
            if (pi_max[i] > max_len) { // checar si el actual mejora la longitud
                max_len = pi_max[i];
                ini_b = i-pi_max[i]+1;
                ini_a = -1;
                rev = false;
            }
        }
        if (pi_max_rev[i] != 0 && pi_max_rev[i] >= pi_max_rev[i+1]) {
//            r_rev.push_back({i-pi_max_rev[i]+1, pi_max_rev[i]});
            if (pi_max_rev[i] > max_len) { // checar si el actual mejora la longitud
                max_len = pi_max_rev[i];
                ini_b = i-pi_max_rev[i]+1;
                ini_a = -1;
                rev = true;
            }
        }

    }

//    /// probar todos los pares consecutivos posibles y/o agarrar el maximo (comparando con i)

//    for (i=0; i<r.size()-2; i++) {
//
//        if (r[i+1].first+r[i+1].second != r[i].first) // por posicion, no es posible
//            continue;
//
//        len = r[i].second + r[i+1].second;
//        if (len <= max_len || len > n) // la longitud no mejora o no es posible
//            continue;
//
//        pos_a = encontrar(b.substr(r[i].first,r[i].second) + b.substr(r[i+1].first,r[i+1].second));
//        if (pos_a == -1) // no existe el substring en a
//            continue;
//
//        max_len = len;
//        ini_a = pos_a;
//        ini_b = r[i].first;
//
//    }

//    for (i=0; i<r_rev.size()-2; i++) {
//
//        if (r_rev[i+1].first+r_rev[i+1].second != r_rev[i].first) // por posicion, no es posible
//            continue;
//
//        len = r_rev[i+1].second + r_rev[i].second;
//        if (len <= max_len || len > n) // la longitud no mejora o no es posible
//            continue;
//
//        pos_a = encontrar(b_rev.substr(r_rev[i].first,r_rev[i].second) + b_rev.substr(r_rev[i+1].first,r_rev[i+1].second));
//        if (pos_a == -1) // no existe el substring en a
//            continue;
//
//        max_len = len;
//        ini_a = pos_a;
//        ini_b = m-r_rev[i+1].first-len;
//
//    }

    if (ini_a == -1) {
        if (!rev) {
            ini_a = encontrar(b.substr(ini_b, max_len));
        } else {
            ini_a = encontrar(b_rev.substr(ini_b, max_len));
            ini_b = m - ini_b - max_len;
        }
    }
    if (sw) swap(ini_a, ini_b);

    cout << max_len << '\n' << ini_a << ' ' << ini_b;

    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40