文字列/Knuth–Morris–Pratt algorithm
(test/string/knuth-morris-pratt.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B

Depends on

• Knuth–Morris–Pratt algorithm (include/emthrm/string/knuth-morris-pratt.hpp)

Code

/*
 * @title 文字列/Knuth–Morris–Pratt algorithm
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
 */

#include <iostream>
#include <string>

#include "emthrm/string/knuth-morris-pratt.hpp"

int main() {
  std::string t, p;
  std::cin >> t >> p;
  for (const int ans : emthrm::KnuthMorrisPratt<>(p).match(t)) {
    std::cout << ans << '\n';
  }
  return 0;
}

#line 1 "test/string/knuth-morris-pratt.test.cpp"
/*
 * @title 文字列/Knuth–Morris–Pratt algorithm
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
 */

#include <iostream>
#include <string>

#line 1 "include/emthrm/string/knuth-morris-pratt.hpp"



#line 5 "include/emthrm/string/knuth-morris-pratt.hpp"
#include <vector>

namespace emthrm {

template <typename T = std::string>
struct KnuthMorrisPratt {
  std::vector<int> border;

  explicit KnuthMorrisPratt(const T& s) : s(s) {
    const int n = s.size();
    border.assign(n + 1, -1);
    for (int i = 0, j = -1; i < n; ++i) {
      while (j >= 0 && s[i] != s[j]) j = border[j];
      ++j;
      border[i + 1] = (i + 1 < n && s[i + 1] == s[j] ? border[j] : j);
    }
  }

  std::vector<int> match(const T& t) const {
    const int n = s.size(), m = t.size();
    std::vector<int> res;
    for (int i = 0, k = 0; i < m; ++i) {
      while (k >= 0 && t[i] != s[k]) k = border[k];
      if (++k == n) res.emplace_back(i - n + 1);
    }
    return res;
  }

 private:
  const T s;
};

}  // namespace emthrm


#line 11 "test/string/knuth-morris-pratt.test.cpp"

int main() {
  std::string t, p;
  std::cin >> t >> p;
  for (const int ans : emthrm::KnuthMorrisPratt<>(p).match(t)) {
    std::cout << ans << '\n';
  }
  return 0;
}

Back to top page