ランレングス圧縮 (連長圧縮, Run Length Encoding, RLE)
(src/sequence/run-length-encoding.hpp)

• View this file on GitHub
• Last update: 2023-08-11 19:35:51+09:00
• Include: #include "src/sequence/run-length-encoding.hpp"

run_length_encoding

(1) std::vector< std::pair< T, usize > >
    run_length_encoding<T, Iter>(Iter first, Iter last)

(2) std::vector< std::pair< T, usize > >
    run_length_encoding<T>(const std::vector<T> &vs)

(3) std::vector< std::pair< char, usize > >
    run_length_encoding<T>(const std::string &s)

• (1) イテレータによる区間 $[first, last)$ をランレングス圧縮した結果を返す。
• (2) std::vector<T> をランレングス圧縮した結果を返す。
• (3) std::string をランレングス圧縮した結果を返す。

ランレングス圧縮の結果は (値, 個数) を要素とする std::vector で返される。

計算量

要素数を $n$ として $O(n)$

Depends on

• size alias (src/cpp-template/header/size-alias.hpp)

Verified with

• test/atcoder/abc259_c.test.cpp

Code

#pragma once

#include "src/cpp-template/header/size-alias.hpp"

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

namespace luz {

  template < class T, class Iter >
  std::vector< std::pair< T, usize > > run_length_encoding(
      Iter first, Iter last) {
    std::vector< std::pair< T, usize > > result;

    while (first != last) {
      if (result.empty() or result.back().first != *first) {
        result.emplace_back(*first, 0);
      }

      result.back().second++;
      ++first;
    }

    return result;
  }

  template < typename T >
  std::vector< std::pair< T, usize > > run_length_encoding(
      const std::vector< T > &vs) {
    return run_length_encoding(vs.begin(), vs.end());
  }

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

} // namespace luz

#line 2 "src/sequence/run-length-encoding.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/sequence/run-length-encoding.hpp"

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

namespace luz {

  template < class T, class Iter >
  std::vector< std::pair< T, usize > > run_length_encoding(
      Iter first, Iter last) {
    std::vector< std::pair< T, usize > > result;

    while (first != last) {
      if (result.empty() or result.back().first != *first) {
        result.emplace_back(*first, 0);
      }

      result.back().second++;
      ++first;
    }

    return result;
  }

  template < typename T >
  std::vector< std::pair< T, usize > > run_length_encoding(
      const std::vector< T > &vs) {
    return run_length_encoding(vs.begin(), vs.end());
  }

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

} // namespace luz

Back to top page