部分列 DP
(include/emthrm/string/subsequence_dp.hpp)

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/string/subsequence_dp.hpp"

時間計算量

$O(\sigma \lvert S \rvert)$

仕様

名前	戻り値
std::vector<std::vector<int>> subsequence_dp(const std::string& s, const char basis = 'a', const int sigma = 26);	$S$ の $i$ 文字目以降 (inclusive) で最初に文字 $c$ が現れるインデックス

参考文献

• https://qiita.com/drken/items/a207e5ae3ea2cf17f4bd

Submissons

https://atcoder.jp/contests/arc081/submissions/26043202

Verified with

• 文字列/部分列 DP (test/string/subsequence_dp.test.cpp)

Code

#ifndef EMTHRM_STRING_SUBSEQUENCE_DP_HPP_
#define EMTHRM_STRING_SUBSEQUENCE_DP_HPP_

#include <algorithm>
#include <string>
#include <vector>

namespace emthrm {

std::vector<std::vector<int>> subsequence_dp(
    const std::string& s, const char basis = 'a', const int sigma = 26) {
  const int n = s.length();
  std::vector<std::vector<int>> nx(n, std::vector<int>(sigma, n));
  nx[n - 1][s[n - 1] - basis] = n - 1;
  for (int i = n - 2; i >= 0; --i) {
    std::copy(nx[i + 1].begin(), nx[i + 1].end(), nx[i].begin());
    nx[i][s[i] - basis] = i;
  }
  return nx;
}

}  // namespace emthrm

#endif  // EMTHRM_STRING_SUBSEQUENCE_DP_HPP_

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



#include <algorithm>
#include <string>
#include <vector>

namespace emthrm {

std::vector<std::vector<int>> subsequence_dp(
    const std::string& s, const char basis = 'a', const int sigma = 26) {
  const int n = s.length();
  std::vector<std::vector<int>> nx(n, std::vector<int>(sigma, n));
  nx[n - 1][s[n - 1] - basis] = n - 1;
  for (int i = n - 2; i >= 0; --i) {
    std::copy(nx[i + 1].begin(), nx[i + 1].end(), nx[i].begin());
    nx[i][s[i] - basis] = i;
  }
  return nx;
}

}  // namespace emthrm

Back to top page