ランレングス圧縮
(library/string/run_length.hpp)

• View this file on GitHub
• Last update: 2026-01-07 21:05:45+09:00
• Include: #include "library/string/run_length.hpp"

ランレングス圧縮

できること

• 文字の連続数で圧縮する

  AAAABBBCDDDD
  ↓
  { [A, 4], [B, 3], [C, 1], [D, 4] }
  

計算量

$O(\vert S \vert)$

使い方

vector<pair<char, int>> R = run_length(S);

Verified with

• ランレングス圧縮のテスト (tests/string.run_length.test.cpp)

Code

#pragma once
vector<pair<char, int>> run_length(const string &S) {
    vector<pair<char, int>> res;
    for (auto &&x : S) {
        if (res.empty() or res.back().first != x) res.emplace_back(x, 0);
        ++res.back().second;
    }
    return res;
}

#line 2 "library/string/run_length.hpp"
vector<pair<char, int>> run_length(const string &S) {
    vector<pair<char, int>> res;
    for (auto &&x : S) {
        if (res.empty() or res.back().first != x) res.emplace_back(x, 0);
        ++res.back().second;
    }
    return res;
}

Back to top page