string/is_substring.hpp

• View this file on GitHub
• Last update: 2022-10-12 08:06:00+09:00
• Include: #include "string/is_substring.hpp"

Depends on

• string/zalgorithm.hpp

Verified with

• test/mytest/is_substring.test.cpp
• test_atcoder/abc237ex.test.cpp
• test_atcoder/abc279b.test.cpp

Code

#include "string/zalgorithm.hpp"

// 連続部分列に含むかどうか。z-algo で線形時間
template <typename STRING>
bool is_substring(STRING& S, STRING& T) {
  int n = int(S.size()), m = int(T.size());
  STRING ST;
  for (auto&& x: S) ST.push_back(x);
  for (auto&& x: T) ST.push_back(x);
  auto Z = zalgorithm(ST);
  for (int i = n; i < n + m; ++i) {
    if (Z[i] >= n) return true;
  }
  return false;
}

#line 1 "string/zalgorithm.hpp"
template <typename STRING>  // string, vector どちらでも
vector<int> zalgorithm(const STRING& s) {
  int n = int(s.size());
  if (n == 0) return {};
  vector<int> z(n);
  z[0] = 0;
  for (int i = 1, j = 0; i < n; i++) {
    int& k = z[i];
    k = (j + z[j] <= i) ? 0 : min(j + z[j] - i, z[i - j]);
    while (i + k < n && s[k] == s[i + k]) k++;
    if (j + z[j] < i + z[i]) j = i;
  }
  z[0] = n;
  return z;
}
#line 2 "string/is_substring.hpp"

// 連続部分列に含むかどうか。z-algo で線形時間
template <typename STRING>
bool is_substring(STRING& S, STRING& T) {
  int n = int(S.size()), m = int(T.size());
  STRING ST;
  for (auto&& x: S) ST.push_back(x);
  for (auto&& x: T) ST.push_back(x);
  auto Z = zalgorithm(ST);
  for (int i = n; i < n + m; ++i) {
    if (Z[i] >= n) return true;
  }
  return false;
}

Back to top page