제출 #509830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
509830		kianaRZV	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	25 / 85	1590 ms	78660 KiB

necklace

#include <bits/stdc++.h>
#define ui unsigned int
using namespace std;
const int maxn = 3e3 + 3;
const ui p = 31;
int n, m, ans, res1, res2;
ui  tav[maxn];
string s1, s2;
bool swaped;
map <ui, int> sub;

void mincycle(ui hsh, int l, int r) {
    int sz = r - l;
    sub[hsh] = l;
    for (int i = l; i < r - 1; i++) {
        hsh = hsh - tav[sz] * ((ui)(s1[i] - '`'));
        hsh = p * hsh + (ui)(s1[i] - '`');
        sub[hsh] = l;
    }
}

void read_input() {
    cin >> s1 >> s2;
    if(s1.size() > s2.size())
        swap(s1, s2), swaped = true;
    n = s1.size(), m = s2.size();
}

void solve() {
    tav[0] = 1;
    for(int i = 1; i < maxn; i++) {
        tav[i] = p * tav[i - 1];
    }
    for (int i = 0; i < n; i++) {
        ui hsh = 0;
        for (int j = i; j < n; j++) {
            hsh = hsh * p + (ui)(s1[j] - '`');
            mincycle(hsh, i, j);
        }
    }
    for (int i = 0; i < m; i++) {
        ui hsh = 0;
        for (int j = i; j < m; j++) {
            hsh = p * hsh + (ui)(s2[j] - '`');
            if (sub.count(hsh))
                if (j - i + 1 > ans)
                    ans = j - i + 1, res1 = sub[hsh], res2 = i;
        }
    }
    reverse(s2.begin(), s2.end());
    for (int i = 0; i < m; i++) {
        ui hsh = 0;
        for (int j = i; j < m; j++) {
            hsh = p * hsh + (ui)(s2[j] - '`');
            if (sub.count(hsh))
                if (j - i + 1 > ans)
                    ans = j - i + 1, res1 = sub[hsh], res2 = m - j - 1;
        }
    }
    if(swaped)
        swap(res1, res2);
    cout << ans << '\n' << res1 << ' ' << res2;
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    read_input(), solve();
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40