sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B" #include <bits/stdc++.h> #include "../../string/kmp.hpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); string T; cin >> T; string P; cin >> P; auto ans = kmp(T, P, prefix_function(P)); for (int i : ans) cout << i << "\n"; }
#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 <bits/stdc++.h> #line 4 "string/kmp.hpp" template <typename T> std::vector<int> prefix_function(const std::vector<T>& s) { const int n = s.size(); std::vector<int> ret(n); for (int len = 0, i = 1; i < n; ++i) { if (s[i] == s[len]) { ++len; ret[i] = len; } else { if (len != 0) { len = ret[len - 1]; --i; } else { ret[i] = 0; } } } return ret; } template <typename T> std::vector<int> kmp(const std::vector<T>& txt, const std::vector<T>& pat, const std::vector<int>& pf) { const int n = txt.size(), m = pat.size(); std::vector<int> match; for (int i = 0, j = 0; i < n;) { if (pat[j] == txt[i]) { ++i; ++j; } if (j == m) { match.push_back(i - j); j = pf[j - 1]; } else if (i < n && pat[j] != txt[i]) { if (j != 0) { j = pf[j - 1]; } else { ++i; } } } return match; } std::vector<int> prefix_function(const std::string& s) { return prefix_function(std::vector<char>(s.begin(), s.end())); } std::vector<int> kmp(const std::string& txt, const std::string& pat, const std::vector<int>& pf) { return kmp(std::vector<char>(txt.begin(), txt.end()), std::vector<char>(pat.begin(), pat.end()), pf); } template <int AlphabetSize, int Offset> std::vector<std::vector<std::pair<int, bool>>> matching_automaton( const std::string& s) { const int n = s.size(); auto lps = prefix_function(s); std::vector aut(n, std::vector<std::pair<int, bool>>(AlphabetSize)); for (int i = 0; i < n; ++i) { for (int c = 0; c < AlphabetSize; ++c) { if (Offset + c == s[i]) { if (i == n - 1) { aut[i][c] = {lps[i], true}; } else { aut[i][c] = {i + 1, false}; } } else { aut[i][c] = {i > 0 ? aut[lps[i - 1]][c].first : 0, 0}; } } } return aut; } #line 7 "test/aoj/ALDS1_14_B.kmp.test.cpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); string T; cin >> T; string P; cin >> P; auto ans = kmp(T, P, prefix_function(P)); for (int i : ans) cout << i << "\n"; }