Enumerate Runs
(string/enumerate_runs.hpp)

• View this file on GitHub
• Last update: 2024-01-08 16:18:25+09:00
• Include: #include "string/enumerate_runs.hpp"

Description

文字列の run (部分文字列の繰り返しであって，長さが極大のもの) を列挙する．この実装では Main-Lorentz アルゴリズムを用いている．

Operations

• vector<vector<pair<int, int>> enumerate_runs(string s)
  • 文字列 $s$ の run を列挙する．ret[p] には周期 $p$ の run が含まれている．
  • 時間計算量: $O(n\log n)$

Reference

• Runの列挙 (Main-Lorentz algorithm)

Depends on

• Z Array (string/z_array.hpp)

Verified with

• test/yosupo/runenumerate.test.cpp

Code

#pragma once
#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>

#include "z_array.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 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;
}

Back to top page