Run Enumerate
(lib/string/run_enumerate.hpp)

• View this file on GitHub
• Last update: 2024-10-31 22:40:32+09:00
• Include: #include "lib/string/run_enumerate.hpp"
• Link: https://pazzle1230.hatenablog.com/entry/2019/11/27/234632

Run Enumerate

概要

文字列 $S$ について、Run の列挙を行います。

計算量

$\mathrm{O}(\lvert S\lvert \log \lvert S\lvert)$

Depends on

• Z Algorithm (lib/string/z_algorithm.hpp)

Verified with

• test/library_checker/string/runenumerate.test.cpp

Code

#pragma once

/**
 * @brief Run Enumerate
 * @docs docs/string/run_enumerate.md
 * @see https://pazzle1230.hatenablog.com/entry/2019/11/27/234632
 */

#include "z_algorithm.hpp"

vector<tuple<int, int, int>> run_enumerate(const string &s){
    int n = s.size();
    vector<tuple<int, int, int>> res;
    auto dfs = [&](auto &self, int l, int r) -> void {
        if(r - l < 2){
            return;
        }
        int mid = (l + r) / 2;
        self(self, l, mid);
        self(self, mid, r);

        string ns = s.substr(l, r - l);
        int lenl = mid - l, lenr = r - mid;
        string sl = s.substr(l, lenl);
        reverse(sl.begin(), sl.end());
        string sr = s.substr(mid, lenr);
        sr += ns;
        reverse(ns.begin(), ns.end());
        sl += ns;
        auto zl = z_algorithm(sl);
        auto zr = z_algorithm(sr);
        {
            for(int i = l; i < mid; i++){
                // [i, mid) を周期
                int len = mid - i;
                int nl = i, nr = mid;
                if(i > l) nl = max(l, nl - zl[len]);
                nr = min(r, nr + zr[lenr + (i - l)]);
                if(nr - nl >= len * 2){
                    if(nl >= 1 && s[nl - 1] == s[nl - 1 + len]){
                        continue;
                    }
                    if(nr < n && s[nr] == s[nr - len]){
                        continue;
                    }
                    res.emplace_back(nl, nr, len);
                }
            }
        }
        {
            for(int i = mid + 1; i <= r; i++){
                // [mid, i) を周期
                int len = i - mid;
                int nl = mid, nr = i;
                if(i < r) nr = min(r, nr + zr[len]);
                nl = max(l, nl - zl[lenl + (r - i)]);
                if(nr - nl >= len * 2){
                    if(nl >= 1 && s[nl - 1] == s[nl - 1 + len]){
                        continue;
                    }
                    if(nr < n && s[nr] == s[nr - len]){
                        continue;
                    }
                    res.emplace_back(nl, nr, len);
                }
            }
        }
    };
    dfs(dfs, 0, n);
    sort(res.begin(), res.end());
    vector<tuple<int, int, int>> ans;
    int pl = -1, pr = -1;
    for(auto [l, r, len] : res){
        if(l == pl && r == pr){
            continue;
        }
        pl = l, pr = r;
        ans.emplace_back(len, l, r);
    }
    sort(ans.begin(), ans.end());
    return ans;
}

#line 2 "lib/string/run_enumerate.hpp"

/**
 * @brief Run Enumerate
 * @docs docs/string/run_enumerate.md
 * @see https://pazzle1230.hatenablog.com/entry/2019/11/27/234632
 */

#line 2 "lib/string/z_algorithm.hpp"

/**
 * @brief Z Algorithm
 * @docs docs/string/z_algorithm.md
 */

template <typename T>
vector<int> z_algorithm(const T &s) {
    int n = s.size();
    vector<int> res(n, 0);
    for(int i = 1, j = 0; i < n; ++i){
        if(i + res[i - j] < j + res[j]){
            res[i] = res[i - j];
        } else{
            res[i] = max(j + res[j] - i, 0);
            while(i + res[i] < n && s[i + res[i]] == s[res[i]]) ++res[i];
            j = i;
        }
    }
    res[0] = n;
    return res;
}
#line 10 "lib/string/run_enumerate.hpp"

vector<tuple<int, int, int>> run_enumerate(const string &s){
    int n = s.size();
    vector<tuple<int, int, int>> res;
    auto dfs = [&](auto &self, int l, int r) -> void {
        if(r - l < 2){
            return;
        }
        int mid = (l + r) / 2;
        self(self, l, mid);
        self(self, mid, r);

        string ns = s.substr(l, r - l);
        int lenl = mid - l, lenr = r - mid;
        string sl = s.substr(l, lenl);
        reverse(sl.begin(), sl.end());
        string sr = s.substr(mid, lenr);
        sr += ns;
        reverse(ns.begin(), ns.end());
        sl += ns;
        auto zl = z_algorithm(sl);
        auto zr = z_algorithm(sr);
        {
            for(int i = l; i < mid; i++){
                // [i, mid) を周期
                int len = mid - i;
                int nl = i, nr = mid;
                if(i > l) nl = max(l, nl - zl[len]);
                nr = min(r, nr + zr[lenr + (i - l)]);
                if(nr - nl >= len * 2){
                    if(nl >= 1 && s[nl - 1] == s[nl - 1 + len]){
                        continue;
                    }
                    if(nr < n && s[nr] == s[nr - len]){
                        continue;
                    }
                    res.emplace_back(nl, nr, len);
                }
            }
        }
        {
            for(int i = mid + 1; i <= r; i++){
                // [mid, i) を周期
                int len = i - mid;
                int nl = mid, nr = i;
                if(i < r) nr = min(r, nr + zr[len]);
                nl = max(l, nl - zl[lenl + (r - i)]);
                if(nr - nl >= len * 2){
                    if(nl >= 1 && s[nl - 1] == s[nl - 1 + len]){
                        continue;
                    }
                    if(nr < n && s[nr] == s[nr - len]){
                        continue;
                    }
                    res.emplace_back(nl, nr, len);
                }
            }
        }
    };
    dfs(dfs, 0, n);
    sort(res.begin(), res.end());
    vector<tuple<int, int, int>> ans;
    int pl = -1, pr = -1;
    for(auto [l, r, len] : res){
        if(l == pl && r == pr){
            continue;
        }
        pl = l, pr = r;
        ans.emplace_back(len, l, r);
    }
    sort(ans.begin(), ans.end());
    return ans;
}

Back to top page