Submission #446596

#	Time	Username	Problem	Language	Result	Execution time	Memory
446596		Mamedov	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	25 / 85	1597 ms	94320 KiB

necklace

#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 = 421279;
const int mod = 2100003007;

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;

    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);
        }
    }

    reverse(a.begin(), a.end());

    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(n - 1 - j, 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;
                }
            }
        }
    }
    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