test/yosupo/runenumerate.test.cpp

View this file on GitHub
Last update: 2024-01-08 16:18:25+09:00
Problem: https://judge.yosupo.jp/problem/runenumerate

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/runenumerate"

#include "../../string/enumerate_runs.hpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string S;
    cin >> S;
    auto runs = enumerate_runs(S);
    vector<tuple<int, int, int>> ans;
    set<pair<int, int>> used;
    for (int p = 1; p <= S.size(); ++p) {
        for (auto [l, r] : runs[p]) {
            if (!used.count({l, r})) {
                used.insert({l, r});
                ans.push_back({p, l, r});
            }
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (auto [t, l, r] : ans) {
        cout << t << " " << l << " " << r << "\n";
    }
}

#line 1 "test/yosupo/runenumerate.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/runenumerate"

#line 2 "string/enumerate_runs.hpp"
#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>

#line 2 "string/z_array.hpp"
#include <string>
#line 4 "string/z_array.hpp"

std::vector<int> z_array(const std::string& s) {
    const int n = s.size();
    std::vector<int> z(n);
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        int k = i - l;
        if (i <= r && z[k] < r - i + 1) {
            z[i] = z[k];
        } else {
            l = i;
            if (i > r) r = i;
            while (r < n && s[r - l] == s[r]) ++r;
            --r;
            z[i] = r - l + 1;
        }
    }
    return z;
}
#line 8 "string/enumerate_runs.hpp"

std::vector<std::vector<std::pair<int, int>>> enumerate_runs(
    const std::string& s) {
    std::vector<std::vector<std::pair<int, int>>> runs(s.size() + 1);

    auto calc = [&](const std::string& u, const std::string& v) {
        const int nu = u.size(), nv = v.size();
        std::string ru(u.rbegin(), u.rend());
        auto z1 = z_array(ru);
        auto z2 = z_array(v + '$' + u + v);
        std::vector<std::tuple<int, int, int>> res;
        for (int i = 0; i < nu; ++i) {
            int period = nu - i;
            int left = period + (i > 0 ? z1[nu - i] : 0);
            int right = z2[nv + 1 + i];
            if (2 * period <= left + right) {
                res.emplace_back(nu - left, nv - right, period);
            }
        }
        return res;
    };

    auto rec = [&](auto& rec, int l, int r) {
        if (r - l == 1) return;
        int m = std::midpoint(l, r);
        rec(rec, l, m);
        rec(rec, m, r);

        std::string u(s.begin() + l, s.begin() + m);
        std::string v(s.begin() + m, s.begin() + r);
        for (auto [a, b, p] : calc(u, v)) {
            runs[p].emplace_back(l + a, r - b);
        }

        std::string ru(u.rbegin(), u.rend());
        std::string rv(v.rbegin(), v.rend());
        for (auto [a, b, p] : calc(rv, ru)) {
            runs[p].emplace_back(l + b, r - a);
        }
    };

    rec(rec, 0, s.size());

    // remove duplicates
    for (int p = 1; p <= (int)s.size(); ++p) {
        std::ranges::sort(runs[p], [&](auto& p, auto& q) {
            return std::make_pair(p.first, -p.second) <
                   std::make_pair(q.first, -q.second);
        });
        std::vector<std::pair<int, int>> res;
        int mx = -1;
        for (auto [l, r] : runs[p]) {
            if (r <= mx) continue;
            mx = r;
            res.emplace_back(l, r);
        }
        runs[p].swap(res);
    }
    return runs;
}
#line 4 "test/yosupo/runenumerate.test.cpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string S;
    cin >> S;
    auto runs = enumerate_runs(S);
    vector<tuple<int, int, int>> ans;
    set<pair<int, int>> used;
    for (int p = 1; p <= S.size(); ++p) {
        for (auto [l, r] : runs[p]) {
            if (!used.count({l, r})) {
                used.insert({l, r});
                ans.push_back({p, l, r});
            }
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (auto [t, l, r] : ans) {
        cout << t << " " << l << " " << r << "\n";
    }
}