제출 #1328281

#제출 시각아이디문제언어결과실행 시간메모리
1328281ashrafyousryNecklace (Subtask 4) (BOI19_necklace4)C++20
0 / 15
282 ms544 KiB
#include <bits/stdc++.h>
using namespace std;

vector<int> kmp(string v) {
    int n = v.size();
    vector<int> fail(n);
    for (int i = 1, j = 0; i < n; ++i) {
        while (j > 0 && v[i] != v[j]) {
            j = fail[j - 1];
        }
        j += (v[i] == v[j]);
        fail[i] = j;
    }
    return fail;
}

int ans, a_pos, b_pos;

void calc(string a, string b, bool flag) {

    int a_sz = a.size(), b_sz = b.size();
    string rev_b = b;
    reverse(rev_b.begin(), rev_b.end());
    for (int i = 0; i < a_sz; ++i) {

        string s1 = a.substr(0, i + 1);
        string s2 = (i + 1 < a_sz ? a.substr(i + 1) : "");
        reverse(s1.begin(), s1.end());

        vector<int> first = kmp(s1 + rev_b), second = kmp(s2 + b);
        first = vector<int>(first.end() - b_sz, first.end());
        second = vector<int>(second.end() - b_sz, second.end());

        for (int j = 0; j < b_sz; ++j) {
            int s2_val = (b_sz - j - 2 >= 0 ? second[b_sz - j - 2] : 0);
            int val = first[j] + s2_val;
            if (val > ans) {
                ans = val;
                a_pos = i - first[j] + 1;
                b_pos = b_sz - j - 1 - s2_val;
                if (flag) {
                    b_pos = b_sz - b_pos - val;
                }
            }
        }
    }

}

void solve() {

    string a, b;
    cin >> a >> b;
    calc(a, b, false);
    reverse(b.begin(), b.end());
    calc(a, b, true);
    cout << ans << "\n" << a_pos << " " << b_pos;

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
        if (t) cout << "\n";
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...