test/aizu-online-judge/ALDS1_14_B.test.cpp

View this file on GitHub
Last update: 2021-05-27 01:59:50+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B

Depends on

Knuth-Morris-Pratt Algorithm (src/string/kmp.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B"

#include <algorithm>
#include <cassert>
#include <iostream>

#include "src/string/kmp.hpp"

int main() {
  using namespace workspace;

  std::string t, p;
  std::cin >> t >> p;
  auto b = mp_algorithm(p + '$' + t);
  auto sb = kmp_algorithm(p + '$' + t);
  for (size_t i = 0, j = p.size() * 2 + 1; j < b.size(); ++i, ++j)
    if (b[j] == p.size()) {
      assert(sb[j] == p.size());
      std::cout << i << "\n";
    } else
      assert(sb[j] != p.size());
}

#line 1 "test/aizu-online-judge/ALDS1_14_B.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B"

#include <algorithm>
#include <cassert>
#include <iostream>

#line 2 "src/string/kmp.hpp"

/**
 * @file kmp.hpp
 * @brief Knuth-Morris-Pratt Algorithm
 */

#include <vector>

namespace workspace {

/**
 * @brief Morris-Pratt algorithm.
 *
 * @param __s String
 * @return Border array of given string.
 */
template <class _String> auto mp_algorithm(const _String& __s) {
  std::vector<size_t> __b(__s.size() + 1);
  for (size_t __p{__b[0] = -1}, __q{}; __q != __s.size(); __b[++__q] = ++__p)
    while (~__p && __s[__p] != __s[__q]) __p = __b[__p];
  return __b;
}

/**
 * @brief Knuth-Morris-Pratt algorithm.
 *
 * @param __s String
 * @return Strong-border array of given string.
 */
template <class _String> auto kmp_algorithm(const _String& __s) {
  auto __b = mp_algorithm(__s);
  for (size_t __i{1}; __i != __s.size(); ++__i)
    if (__s[__i] == __s[__b[__i]]) __b[__i] = __b[__b[__i]];
  return __b;
}

}  // namespace workspace
#line 8 "test/aizu-online-judge/ALDS1_14_B.test.cpp"

int main() {
  using namespace workspace;

  std::string t, p;
  std::cin >> t >> p;
  auto b = mp_algorithm(p + '$' + t);
  auto sb = kmp_algorithm(p + '$' + t);
  for (size_t i = 0, j = p.size() * 2 + 1; j < b.size(); ++i, ++j)
    if (b[j] == p.size()) {
      assert(sb[j] == p.size());
      std::cout << i << "\n";
    } else
      assert(sb[j] != p.size());
}