string/count_subseq.hpp

• View this file on GitHub
• Last update: 2023-10-17 19:59:15+09:00
• Include: #include "string/count_subseq.hpp"
• Link: https://noshi91.hatenablog.com/entry/2023/02/26/135340

Verified with

• test/library_checker/string/number_of_subsequences.test.cpp
• test/yukicoder/1493.test.cpp

Code

// https://noshi91.hatenablog.com/entry/2023/02/26/135340
template <typename mint, typename STRING>
mint count_subseq(STRING& S) {
  map<int, mint> dp;
  mint sm = 1;
  for (auto&& x: S) {
    auto it = dp.find(x);
    if (it == dp.end()) {
      dp[x] = sm;
      sm += sm;
    } else {
      mint d = (*it).se;
      (*it).se = sm;
      sm += sm - d;
    }
  }
  return sm;
}

#line 1 "string/count_subseq.hpp"
// https://noshi91.hatenablog.com/entry/2023/02/26/135340
template <typename mint, typename STRING>
mint count_subseq(STRING& S) {
  map<int, mint> dp;
  mint sm = 1;
  for (auto&& x: S) {
    auto it = dp.find(x);
    if (it == dp.end()) {
      dp[x] = sm;
      sm += sm;
    } else {
      mint d = (*it).se;
      (*it).se = sm;
      sm += sm - d;
    }
  }
  return sm;
}

Back to top page