제출 #1275260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275260		mahesh_9996	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	219 ms	504 KiB

necklace

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

vector<int> compute_prefix(const string &s) {
    int n = (int)s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

void solve_no_struct(const string &s, const string &t, bool r, int &score_out, int &a_out, int &b_out) {
    int n = (int)s.size();
    int m = (int)t.size();

    string T1 = t;
    reverse(T1.begin(), T1.end());

    string R1 = string("?") + T1;      // we'll prepend chars from s each iteration
    string R2 = s + string("?") + t;   // we'll erase first char each iteration

    int bestScore = 0;
    int bestA = -1, bestB = -1;

    for (int i = 0; i < n; ++i) {
        R1.insert(R1.begin(), s[i]);
        R2.erase(R2.begin());

        vector<int> pi1 = compute_prefix(R1);
        vector<int> pi2 = compute_prefix(R2);

        for (int j = -1; j < m; ++j) {
            int idx1 = i + m - j;
            int idx2 = n - i + j;

            int x = 0;
            if (0 <= idx1 && idx1 < (int)pi1.size()) x = pi1[idx1];
            int y = 0;
            if (0 <= idx2 && idx2 < (int)pi2.size()) y = pi2[idx2];

            if (x + y > bestScore) {
                bestScore = x + y;
                bestA = (r ? n - (i + y) - 1 : i - x + 1);
                bestB = j - y + 1;
            }
        }
    }

    score_out = bestScore;
    a_out = bestA;
    b_out = bestB;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    if (!(cin >> s >> t)) return 0;

    int res1, a1, b1;
    solve_no_struct(s, t, false, res1, a1, b1);

    string s_rev = s;
    reverse(s_rev.begin(), s_rev.end());

    int res2, a2, b2;
    solve_no_struct(s_rev, t, true, res2, a2, b2);

    // choose lexicographically larger triple (score, a, b)
    int final_res = res1, final_a = a1, final_b = b1;
    if (res2 > final_res
        || (res2 == final_res && (a2 > final_a
            || (a2 == final_a && b2 > final_b)))) {
        final_res = res2;
        final_a = a2;
        final_b = b2;
    }

    cout << final_res << '\n';
    cout << final_a << ' ' << final_b << '\n';
    return 0;
}

• Subtask 1: 15 / 15