test/aoj_ALDS1_14_B_kmp.test.cpp

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

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

#include "String/knuth_morris_pratt_searcher.cpp"

int main() {
  char buf[1048576];
  scanf("%s", buf);
  std::string t = buf;
  scanf("%s", buf);
  std::string p = buf;

  knuth_morris_pratt_searcher kmp(p.begin(), p.end());
  bool matched = false;
  for (auto tmp: kmp.find_all(t.begin(), t.end())) {
    matched = true;
    auto first = tmp.first;
    printf("%td\n", first-t.begin());
  }

  {
    auto first = std::search(t.begin(), t.end(), kmp);
    if (matched != (first != t.end())) return 1;
  }
}

#line 1 "test/aoj_ALDS1_14_B_kmp.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

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

#line 1 "String/knuth_morris_pratt_searcher.cpp"



/**
 * @brief KMP 法
 * @author えびちゃん
 */

#include <cstddef>
#line 11 "String/knuth_morris_pratt_searcher.cpp"

template <typename RandomIt1>
class knuth_morris_pratt_searcher {
public:
  using size_type = size_t;

private:
  static constexpr size_type S_npos = -1;
  RandomIt1 M_pf, M_pl;
  std::vector<size_type> M_fail;

public:
  knuth_morris_pratt_searcher(RandomIt1 pat_first, RandomIt1 pat_last):
    M_pf(pat_first), M_pl(pat_last), M_fail(M_pl-M_pf+1)
  {
    M_fail[0] = S_npos;
    size_type n = M_pl - M_pf;
    for (size_type i = 0, j = S_npos; i < n;) {
      while (j != S_npos && M_pf[i] != M_pf[j]) j = M_fail[j];
      ++i, ++j;
      M_fail[i] = ((i < n && (M_pf[i] == M_pf[j]))? M_fail[j]: j);
    }
  }

  template <typename RandomIt2>
  std::pair<RandomIt2, RandomIt2> find_first(RandomIt2 first, RandomIt2 last) const {
    if (M_pf == M_pl) return {first, first};
    size_type n = M_pl - M_pf;
    size_type j = 0;
    for (auto it = first; it < last;) {
      while (j != S_npos && M_pf[j] != *it) j = M_fail[j];
      ++it;
      if (++j == n) return {it-n, it};
    }
    return {last, last};
  }

  template <typename RandomIt2>
  std::vector<std::pair<RandomIt2, RandomIt2>> find_all(RandomIt2 first, RandomIt2 last) const {
    std::vector<std::pair<RandomIt2, RandomIt2>> res;
    if (M_pf == M_pl) {
      for (auto it = first; it < last; ++it) res.emplace_back(it, it);
      res.emplace_back(last, last);
      return res;
    }

    size_type n = M_pl - M_pf;
    size_type j = 0;
    for (auto it = first; it < last;) {
      while (j != S_npos && M_pf[j] != *it) j = M_fail[j];
      ++it;
      if (++j == n) {
        res.emplace_back(it-n, it);
        j = M_fail[j];
      }
    }
    return res;
  }

  template <typename RandomIt2>
  std::pair<RandomIt2, RandomIt2> operator ()(RandomIt2 first, RandomIt2 last) const {
    return find_first(first, last);
  }

  size_type operator [](size_type i) const { return M_fail[i]; }
};

#if __cplusplus >= 201703L
template <typename RandomIt1>
knuth_morris_pratt_searcher(RandomIt1 pat_first, RandomIt1 pat_last)
  -> knuth_morris_pratt_searcher<RandomIt1>;
#endif


#line 9 "test/aoj_ALDS1_14_B_kmp.test.cpp"

int main() {
  char buf[1048576];
  scanf("%s", buf);
  std::string t = buf;
  scanf("%s", buf);
  std::string p = buf;

  knuth_morris_pratt_searcher kmp(p.begin(), p.end());
  bool matched = false;
  for (auto tmp: kmp.find_all(t.begin(), t.end())) {
    matched = true;
    auto first = tmp.first;
    printf("%td\n", first-t.begin());
  }

  {
    auto first = std::search(t.begin(), t.end(), kmp);
    if (matched != (first != t.end())) return 1;
  }
}