ランレングス圧縮 (run length encoding)
(include/emthrm/string/run_length_encoding.hpp)

• View this file on GitHub
• Last update: 2023-07-07 02:42:02+09:00
• Include: #include "emthrm/string/run_length_encoding.hpp"

時間計算量

$O(\lvert S \rvert)$

仕様

名前	戻り値
template <typename T = char, typename U> requires requires { typename T::value_type; } std::vector<std::pair<typename T::value_type, int>> run_length_encoding(const T& s);	$S$ のランレングス圧縮

Submissons

https://atcoder.jp/contests/abc143/submissions/9291464

Verified with

• 文字列/ランレングス圧縮 (test/string/run_length_encoding.test.cpp)

Code

#ifndef EMTHRM_STRING_RUN_LENGTH_ENCODING_HPP_
#define EMTHRM_STRING_RUN_LENGTH_ENCODING_HPP_

#include <utility>
#include <vector>

namespace emthrm {

template <typename T>
requires requires { typename T::value_type; }
std::vector<std::pair<typename T::value_type, int>> run_length_encoding(
    const T& s) {
  const int n = s.size();
  std::vector<std::pair<typename T::value_type, int>> res;
  if (n == 0) [[unlikely]] return res;
  typename T::value_type ch = s.front();
  int num = 1;
  for (int i = 1; i < n; ++i) {
    if (s[i] != ch) {
      res.emplace_back(ch, num);
      num = 0;
    }
    ch = s[i];
    ++num;
  }
  res.emplace_back(ch, num);
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_STRING_RUN_LENGTH_ENCODING_HPP_

#line 1 "include/emthrm/string/run_length_encoding.hpp"



#include <utility>
#include <vector>

namespace emthrm {

template <typename T>
requires requires { typename T::value_type; }
std::vector<std::pair<typename T::value_type, int>> run_length_encoding(
    const T& s) {
  const int n = s.size();
  std::vector<std::pair<typename T::value_type, int>> res;
  if (n == 0) [[unlikely]] return res;
  typename T::value_type ch = s.front();
  int num = 1;
  for (int i = 1; i < n; ++i) {
    if (s[i] != ch) {
      res.emplace_back(ch, num);
      num = 0;
    }
    ch = s[i];
    ++num;
  }
  res.emplace_back(ch, num);
  return res;
}

}  // namespace emthrm

Back to top page