ランレングス圧縮 (String/run_length_encode.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-05-02 22:16:20+09:00
• Include: #include "String/run_length_encode.hpp"

ランレングス圧縮

連続する同じ要素をまとめて、要素とその出現回数のペア列に変換します。

run_length_encode

template <typename Container>
vector<pair<typename Container::value_type, int>> run_length_encode(const Container &v)

連続する同一要素を1つのペアにまとめ、元のコンテナを走査して圧縮されたペア列を返します。

計算量

• $O(n)$

Verified with

• test/String/run_length_encode/hackerrank-run-length-encoding.cpp
• test/String/run_length_encode/yukicoder-0203.cpp

Code

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

template <typename Container>
vector<pair<typename Container::value_type, int>> run_length_encode(const Container &v)
{
    using T = typename Container::value_type;
    vector<pair<T, int>> result;

    for (const auto &n : v)
    {
        if (result.empty() || result.back().first != n)
        {
            result.push_back({n, 0});
        }

        result.back().second++;
    }

    return result;
}

#line 1 "String/run_length_encode.hpp"
#include <bits/stdc++.h>
using namespace std;

template <typename Container>
vector<pair<typename Container::value_type, int>> run_length_encode(const Container &v)
{
    using T = typename Container::value_type;
    vector<pair<T, int>> result;

    for (const auto &n : v)
    {
        if (result.empty() || result.back().first != n)
        {
            result.push_back({n, 0});
        }

        result.back().second++;
    }

    return result;
}

Back to top page