C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @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; }