Submission #645923

#	Time	Username	Problem	Language	Result	Execution time	Memory
645923		alextodoran	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	497 ms	98552 KiB

necklace

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int L_MAX = 3000;

string a, b;
int n, m;

int lcp[L_MAX + 2][L_MAX + 2];

int kmp[L_MAX + 2][L_MAX + 2];
int lce[L_MAX + 2][L_MAX + 2];

vector <int> solve () {
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            lcp[i][j] = (a[i] == b[j] ? lcp[i + 1][j + 1] + 1 : 0);
        }
    }
    for (int i = 0; i < n; i++) {
        kmp[i][i] = 0;
        for (int j = i + 1; j < n; j++) {
            kmp[i][j] = kmp[i][j - 1];
            while (kmp[i][j] > 0 && a[i + kmp[i][j]] != a[j]) {
                kmp[i][j] = kmp[i][i + kmp[i][j] - 1];
            }
            if (a[i + kmp[i][j]] == a[j]) {
                kmp[i][j]++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        lce[i][0] = (a[i] == b[0] ? 1 : 0);
        for (int j = 1; j < m; j++) {
            lce[i][j] = lce[i][j - 1];
            while (lce[i][j] > 0 && a[i + lce[i][j]] != b[j]) {
                lce[i][j] = kmp[i][i + lce[i][j] - 1];
            }
            if (a[i + lce[i][j]] == b[j]) {
                lce[i][j]++;
            }
        }
    }
    vector <int> best = {0, 0, 0};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x = lcp[i][j];
            int y = 0;
            if (i + x < n && j - 1 >= 0) {
                y = lce[i + x][j - 1];
            }
            vector <int> here = {x + y, i, j - y};
            if (here[0] > best[0]) {
                best = here;
            }
        }
    }
    return best;
}

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

    cin >> a >> b;
    n = (int) a.size(); m = (int) b.size();
    vector <int> best1 = solve();
    reverse(b.begin(), b.end());
    vector <int> best2 = solve();
    best2[2] = m - best2[2] - best2[0];
    if (best1[0] < best2[0]) {
        swap(best1, best2);
    }
    cout << best1[0] << "\n";
    cout << best1[1] << " " << best1[2] << "\n";

    return 0;
}

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