Submission #1350289

#TimeUsernameProblemLanguageResultExecution timeMemory
1350289Br3adNecklace (Subtask 4) (BOI19_necklace4)C++20
15 / 15
200 ms576 KiB
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define pi pair<int, int>
#define vi vector<int>
#define vl vector<ll>

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 3e3 + 5;
const int M = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

const int xMove[4] = {1, 0, -1, 0};
const int yMove[4] = {0, 1, 0, -1};

const int xMoveD[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int yMoveD[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

vi kmp(int len, string &str) {
    vi p(len, 0);
    for (int i = 1; i < len; i++) {
        int cur = p[i-1];
        while (cur > 0 && str[cur] != str[i]) cur = p[cur-1];
        if (str[cur] == str[i]) cur++;
        p[i] = cur;
    }
    return p;
}

void solve(int &ans, int &idx1, int &idx2, string &str1, string &str2, bool is_reverse) {
    bool has_answer = false;
    int n = str1.length(), m = str2.length();

    string str2_reverse = str2;
    reverse(all(str2_reverse));

    for (int i = 0; i < n; i++) {
        string pre = str1.substr(0, i);
        reverse(all(pre));

        string s1 = pre + '.' + str2_reverse;
        string s2 = str1.substr(i) + '.' + str2;

        int len1 = i + m + 1;
        int len2 = n - i + m + 1;

        vi p1 = kmp(len1, s1);
        vi p2 = kmp(len2, s2);

        int len = -1, idx = -1;
        for (int j = 0; j < m; j++) {
            int j1 = i + 1 + (m - j - 1);
            int j2 = n - i + 1 + j - 1;

            int temp = p1[j1] + p2[j2];

            if (temp > ans) {
                has_answer = true;
                idx1 = i - p1[j1];
                idx2 = j - p2[j2];
                ans = temp;
            }
        }
    }

    if (has_answer && is_reverse) idx2 = m - idx2 - ans;

}

int main(){

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

    // ifstream cin();
    // ofstream cout();

    string str1, str2;
    cin >> str1 >> str2;

    string str2_reverse = str2;
    reverse(all(str2_reverse));

    int ans = 0, idx1 = -1, idx2 = -1;
    solve(ans, idx1, idx2, str1, str2, false);
    solve(ans, idx1, idx2, str1, str2_reverse, true);

    cout << ans << endl;
    cout << idx1 << ' ' << idx2 << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...