Submission #584516

#TimeUsernameProblemLanguageResultExecution timeMemory
584516tengiz05Necklace (Subtask 1-3) (BOI19_necklace1)C++17
17 / 85
1471 ms736 KiB
#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

int min_cyc(const string &s) {
    int n = s.size();
    int res = 0;
    for (int l = 0; l < n; ){
        res = l;
        int r = l, p = l + 1;
        for (; r < n; ++r, ++p) /// If there is such string found, then its length wont exceed |s|
        {
            char c = (p < n) ? s[p] : s[p - n]; /// to avoid modulo
            if (s[r] > c) break;
            if (s[r] < c) r = l - 1;
        }        
        l = max(r, l + p - r); /// just skip those (s2 = sx + sx + ... + sx + sy) cases
    }
    return res;
}


struct Hash {
    static constexpr i64 P = 1E12 + 7, M = 29;
    int n;
    i64 x;
    Hash(std::string s) : n(s.size()) {
        x = 0;
        for (int i = 0; i < n; i++)
            x = (1LL * x * M + (s[i] - 'a' + 1)) % P;
    }
    i64 get() {
        return x;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    string a, b;
    cin >> a >> b;
    
    int lo = 0, hi = std::min(a.size(), b.size()) + 1;
    
    auto work = [&](string a, int x) {
        int n = a.size();
        
        vector<pair<i64, int>> b;
        for (int i = 0; i <= n - x; i++) {
            string s = a.substr(i, x);
            int p = min_cyc(s);
            rotate(s.begin(), s.begin() + p, s.end());
            assert(min_cyc(s) == 0);
            b.emplace_back(Hash(s).get(), i);
        }
        
        sort(b.begin(), b.end());
        return b;
    };
    
    auto get = [&](int len) -> pair<int, int> {
        auto x = work(a, len);
        auto y = work(b, len);
        
        int i = 0;
        
        for (auto [a, b] : x) {
            while (i + 1 < int(y.size()) && y[i].first < a) i++;
            if (y[i].first == a) {
                return {b, y[i].second};
            }
        }
        
        return {-1, -1};
    };
    
    while (lo + 1 < hi) {
        int m = (lo + hi) / 2;
        if (get(m).first != -1) {
            lo = m;
        } else {
            hi = m;
        }
    }
    
    auto g = get(lo);
    array<int, 3> ans{lo, g.first, g.second};
    lo = 0, hi = min(a.size(), b.size()) + 1;
    reverse(b.begin(), b.end());
    while (lo + 1 < hi) {
        int m = (lo + hi) / 2;
        if (get(m).first != -1) {
            lo = m;
        } else {
            hi = m;
        }
    }
    
    g = get(lo);
    array<int, 3> res{lo, g.first, int(b.size()) - g.second - lo};
    
    ans = max(ans, res);
    
    cout << ans[0] << "\n";
    cout << ans[1] << " " << ans[2] << "\n";
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...