Submission #1259090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259090		newsboy	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	208 ms	106272 KiB

necklace

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <climits>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <chrono>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;

vector<i64> prefixFunction(string s) {
    i64 n = s.size();
    vector<i64> pi(n);
    for (i64 i = 1; i < n; i++) {
        i64 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;
}

struct T {
    i64 ans, ls, lt;
};

T work(string s, string t, i64 o) {
    i64 n = s.size();
    i64 m = t.size();
    auto g = s + "?" + t;
    vector<vector<i64>> pi(n);
    for (i64 i = 0; i < n; i++) {
        pi[i] = prefixFunction(g.substr(i));
    }
    i64 ans = 0;
    i64 ls = -1, lt = -1;
    for (i64 i = 0; i < n; i++) {
        for (i64 j = 0; j < m; j++) {
            i64 x = pi[i][n - i + 1 + j];
            if (x > ans) {
                ans = x;
                ls = i;
                lt = j - x + 1;
            }
            if (i + x < n && n - (i + x) + 1 + (j - x) < pi[i].size()) {
                i64 y = pi[i + x][n - (i + x) + 1 + (j - x)];
                if (x + y > ans) {
                    ans = x + y;
                    ls = i;
                    lt = (j - x) - y + 1;
                }
            }
        }
    }
    return {ans, (o ? n - (ls + ans - 1) - 1 : ls), lt};
}

void solve() {
    string s, t;
    cin >> s >> t;
    T res1 = work(s, t, 0);
    reverse(s.begin(), s.end());
    T res2 = work(s, t, 1);
    if (res2.ans > res1.ans) {
        res1 = res2;
    }
    cout << res1.ans << '\n';
    cout << res1.ls << " " << res1.lt << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 0 / 15