Submission #645950

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
645950	2022-09-28T10:34:56 Z	alextodoran	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	598 ms	476 KB

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 kmpPrefA[L_MAX + 2];
int kmpSuffA[L_MAX + 2];
int kmpPrefB[L_MAX + 2];
int kmpSuffB[L_MAX + 2];

vector <int> solve () {
    vector <int> best = {0, 0, 0};
    for (int i = 0; i < n; i++) {
        kmpPrefA[i] = 0;
        for (int j = i + 1; j < n; j++) {
            kmpPrefA[j] = kmpPrefA[j - 1];
            while (kmpPrefA[j] > 0 && a[i + kmpPrefA[j]] != a[j]) {
                kmpPrefA[j] = kmpPrefA[i + kmpPrefA[j] - 1];
            }
            if (a[i + kmpPrefA[j]] == a[j]) {
                kmpPrefA[j]++;
            }
        }
        kmpPrefB[0] = (a[i] == b[0] ? 1 : 0);
        for (int j = 1; j < m; j++) {
            kmpPrefB[j] = kmpPrefB[j - 1];
            while (kmpPrefB[j] > 0 && a[i + kmpPrefB[j]] != b[j]) {
                kmpPrefB[j] = kmpPrefA[i + kmpPrefB[j] - 1];
            }
            if (a[i + kmpPrefB[j]] == b[j]) {
                kmpPrefB[j]++;
            }
        }
        if (i > 0) {
            kmpSuffA[i - 1] = 0;
            for (int j = i - 2; j >= 0; j--) {
                kmpSuffA[j] = kmpSuffA[j + 1];
                while (kmpSuffA[j] > 0 && a[(i - 1) - kmpSuffA[j]] != a[j]) {
                    kmpSuffA[j] = kmpSuffA[(i - 1) - kmpSuffA[j] + 1];
                }
                if (a[(i - 1) - kmpSuffA[j]] == a[j]) {
                    kmpSuffA[j]++;
                }
            }
            kmpSuffB[m - 1] = (a[i - 1] == b[m - 1] ? 1 : 0);
            for (int j = m - 2; j >= 0; j--) {
                kmpSuffB[j] = kmpSuffB[j + 1];
                while (kmpSuffB[j] > 0 && a[(i - 1) - kmpSuffB[j]] != b[j]) {
                    kmpSuffB[j] = kmpSuffA[(i - 1) - kmpSuffB[j] + 1];
                }
                if (a[(i - 1) - kmpSuffB[j]] == b[j]) {
                    kmpSuffB[j]++;
                }
            }
        }
        for (int j = 0; j < m; j++) {
            int x = kmpPrefB[j];
            int y = 0;
            if (0 < i && j < m - 1) {
                y = kmpSuffB[j + 1];
            }
            vector <int> here = {x + y, i - y, j - x + 1};
            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

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	559 ms	360 KB	Output is correct
2	Correct	598 ms	356 KB	Output is correct
3	Correct	568 ms	364 KB	Output is correct
4	Correct	456 ms	360 KB	Output is correct
5	Correct	399 ms	444 KB	Output is correct
6	Correct	462 ms	360 KB	Output is correct
7	Correct	467 ms	360 KB	Output is correct
8	Correct	470 ms	356 KB	Output is correct
9	Correct	510 ms	476 KB	Output is correct