RLE (連長圧縮)
(src/algorithm/RLE.hpp)

• View this file on GitHub
• Last update: 2022-09-26 05:14:00+09:00
• Include: #include "src/algorithm/RLE.hpp"

概要

std::vector<std::pair<T, int>> rle(const std::vector<T>& ins)

引数に入れたvectorを連長圧縮します。

例えば、aaabbcdadddは(a, 3)(b, 2)(c, 1)(d, 1)(a, 1)(d, 3)になります。

機能

std::vector<T>かstd::stringを引数にとることができます。

std::stringを引数に入れた場合、std::vector<std::pair<char, int>>が返ります。

計算量

配列の長さを $N$ として $O(N)$

Verified with

• test/RLE.test.cpp

Code

#pragma once

#include <vector>
#include <utility>
#include <string>

namespace zawa {

template <typename T>
std::vector<std::pair<T, int>> rle(const std::vector<T>& ins) {
    std::vector<std::pair<T, int>> res;
    for (size_t i = 0 ; i < ins.size() ; i++) {
        if (res.empty() or res.back().first != ins[i]) {
            res.emplace_back(ins[i], 1);
        }
        else {
            res.back().second++;
        }
    }
    return res;
}

std::vector<std::pair<char, int>> rle(const std::string& s) {
    std::vector<char> in(s.begin(), s.end());
    return rle(in);
}

} // namespace zawa

#line 2 "src/algorithm/RLE.hpp"

#include <vector>
#include <utility>
#include <string>

namespace zawa {

template <typename T>
std::vector<std::pair<T, int>> rle(const std::vector<T>& ins) {
    std::vector<std::pair<T, int>> res;
    for (size_t i = 0 ; i < ins.size() ; i++) {
        if (res.empty() or res.back().first != ins[i]) {
            res.emplace_back(ins[i], 1);
        }
        else {
            res.back().second++;
        }
    }
    return res;
}

std::vector<std::pair<char, int>> rle(const std::string& s) {
    std::vector<char> in(s.begin(), s.end());
    return rle(in);
}

} // namespace zawa

Back to top page