Run length encoding （ランレングス圧縮，連長圧縮）
(utilities/run_length_encoding.hpp)

• View this file on GitHub
• Last update: 2022-07-10 23:01:04+09:00
• Include: #include "utilities/run_length_encoding.hpp"

与えられた std::vector<> や std::string のインスタンスに対してランレングス圧縮を行う．

問題例

• AtCoder Beginner Contest 259 C - XX to XXX

Code

#pragma once
#include <string>
#include <utility>
#include <vector>

// Run length encoding
template <class T> std::vector<std::pair<T, int>> run_length_encoding(const std::vector<T> &v) {
    std::vector<std::pair<T, int>> ret;
    for (const T &x : v) {
        if (ret.empty() or ret.back().first != x) ret.emplace_back(x, 0);
        ++ret.back().second;
    }
    return ret;
}

// aabaacddd -> [(a, 2), (b, 1), (a, 2), (c, 1), (d, 3)]
// Each character in s must be char
std::vector<std::pair<char, int>> run_length_encoding(const std::string &s) {
    std::vector<char> tmp(s.begin(), s.end());
    return run_length_encoding<char>(tmp);
}

#line 2 "utilities/run_length_encoding.hpp"
#include <string>
#include <utility>
#include <vector>

// Run length encoding
template <class T> std::vector<std::pair<T, int>> run_length_encoding(const std::vector<T> &v) {
    std::vector<std::pair<T, int>> ret;
    for (const T &x : v) {
        if (ret.empty() or ret.back().first != x) ret.emplace_back(x, 0);
        ++ret.back().second;
    }
    return ret;
}

// aabaacddd -> [(a, 2), (b, 1), (a, 2), (c, 1), (d, 3)]
// Each character in s must be char
std::vector<std::pair<char, int>> run_length_encoding(const std::string &s) {
    std::vector<char> tmp(s.begin(), s.end());
    return run_length_encoding<char>(tmp);
}

Back to top page