Submission #446608

#TimeUsernameProblemLanguageResultExecution timeMemory
446608MamedovNecklace (Subtask 1-3) (BOI19_necklace1)C++17
45 / 85
1595 ms96532 KiB
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ui unsigned long long
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
#define oo (1ll << 60)

using namespace std;


const int up = 3003;
const ui base = 31;
const int mod = 2100003007;

unordered_map<ui, int>SubHash;

ui pw[up];

void preClc() {
    pw[0] = 1;
    for(int i = 1; i < up; ++i) {
        pw[i] = base * pw[i - 1];
    }
}

string a, b;
int res = 0;
int sa = 0, sb = 0;

void CyclicHashs(ui h, int l, int r) {
    if(SubHash.count(h)) {
        if(res < r - l + 1) {
            res = r - l + 1;
            sa = l;
            sb = SubHash[h];
        }
    }
    for(int i = l; i < r - 1; ++i) {
        h = h - pw[r - l] * (a[i] - '`');
        h = base * h + (a[i] - '`');
        if(SubHash.count(h)) {
            if(res < r - l + 1) {
                res = r - l + 1;
                sa = l;
                sb = SubHash[h];
            }
        }
    }
}
void solve() {
    preClc();
    int n, m;
    cin >> a >> b;

    bool swaped = false;
    if(a.size() > b.size()) {
        swap(a, b);
        swaped = true;
    }

    n = (int)a.size();
    m = (int)b.size();

    for(int i = 0; i < m; ++i) {
        ui h = 0;
        for(int j = i; j < m; ++j) {
            h = base * h + (b[j] - '`');
            SubHash[h] = i;
        }
    }
    reverse(b.begin(), b.end());
    for(int i = 0; i < m; ++i) {
        ui h = 0;
        for(int j = i; j < m; ++j) {
            h = base * h + (b[j] - '`');
            SubHash[h] = m - 1 - j;
        }
    }

    for(int i = 0; i < n; ++i) {
        ui h = 0;
        for(int j = i; j < n; ++j) {
            h = base * h + (a[j] - '`');
            CyclicHashs(h, i, j);
        }
    }

    if(swaped) {
        swap(sa, sb);
    }
    cout << res << '\n';
    cout << sa << ' ' << sb << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...