Submission #1174636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174636		rominanafu	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	0 / 85	1565 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;

int max_len=0, ini_a, ini_b;

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

    cout << pat << endl;

    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);
    }

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

    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;
    if (pi_max[m-1] > 0) r.push_back({m-pi_max[m-1], pi_max[m-1]});
    if (pi_max_rev[m-1] > 0) r_rev.push_back({m-pi_max_rev[m-1], pi_max_rev[m-1]});
    for (i=m-2; 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_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]});

    }

    /// probar todos los pares consecutivos posibles y/o agarrar el maximo (comparando con i)
    int pos_a, len;
    if (r.back().second > max_len) {
        max_len = r.back().second;
        ini_b = r.back().first;
        ini_a = -1;
    }
    for (i=0; i<r.size()-1; i++) {

        if (r[i].second > max_len) { // checar si el actual mejora la longitud
            max_len = r[i].second;
            ini_b = r[i].first;
            ini_a = -1;
        }

        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;

    }

    if (r_rev.back().second > max_len) { // checar si el actual mejora la longitud
        max_len = r_rev.back().second;
        ini_b = m - r_rev.back().first - r_rev.back().second;
        ini_a = -1;
    }
    for (i=0; i<r_rev.size()-1; i++) {

        if (r_rev[i].second > max_len) { // checar si el actual mejora la longitud
            max_len = r_rev[i].second;
            ini_b = m - r_rev[i].first - r_rev[i].second;
            ini_a = -1;
        }

        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)
        ini_a = encontrar(b.substr(ini_b, max_len));

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

    return 0;
}

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