제출 #446600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446600		Mamedov	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	25 / 85	1595 ms	110960 KiB

necklace

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ui unsigned int
#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];
    }
}

void CyclicHashs(int pos, ui h, string &s) {
    string tmp = s + s;
    int sz = (int)s.size();
    SubHash[h] = pos;
    for(int i = sz; i < sz + sz - 1; ++i) {
        h = h - pw[sz - 1] * ((ui)(tmp[i - sz] - '`'));
        h = base * h + (ui)(tmp[i] - '`');
        SubHash[h] = pos;
    }
}
void solve() {
    preClc();
    int n, m;
    string a, b;
    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 all sub-strings store the hash of its lexicographically smallest necklace
    for(int i = 0; i < n; ++i) {
        ui h = 0;
        string s = "";
        for(int j = i; j < n; ++j) {
            h = base * h + (ui)(a[j] - '`');
            s = s + a[j];
            CyclicHashs(i, h, s);
        }
    }

    int res = 0;
    int sa = 0, sb = 0;
    for(int i = 0; i < m; ++i) {
        ui h = 0;
        for(int j = i; j < m; ++j) {
            h = base * h + (ui)(b[j] - '`');
            if(SubHash.count(h)) {
                if(j - i + 1 > res) {
                    res = j - i + 1;
                    sa = SubHash[h];
                    sb = 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 + (ui)(b[j] - '`');
            if(SubHash.count(h)) {
                if(j - i + 1 > res) {
                    res = j - i + 1;
                    sa = SubHash[h];
                    sb = m - 1 - 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;
}

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