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_C" #include <bits/stdc++.h> #include "../../string/pattern_search_2d.hpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int H, W; cin >> H >> W; vector<string> txt(H); for (auto& x : txt) cin >> x; int R, C; cin >> R >> C; vector<string> pat(R); for (auto& x : pat) cin >> x; auto ans = pattern_search_2d(txt, pat); sort(ans.begin(), ans.end()); for (auto [i, j] : ans) { cout << i << " " << j << "\n"; } }
#line 1 "test/aoj/ALDS1_14_C.test.cpp" #define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_C" #include <bits/stdc++.h> #line 4 "string/pattern_search_2d.hpp" #line 8 "string/aho_corasick.hpp" class AhoCorasick { public: struct Node { std::map<char, int> ch; std::vector<int> accept; int link = -1; int cnt = 0; Node() = default; }; std::vector<Node> states; std::map<int, int> accept_state; explicit AhoCorasick() : states(1) {} void insert(const std::string& s, int id = -1) { int i = 0; for (char c : s) { if (!states[i].ch.count(c)) { states[i].ch[c] = states.size(); states.emplace_back(); } i = states[i].ch[c]; } ++states[i].cnt; states[i].accept.push_back(id); accept_state[id] = i; } void clear() { states.clear(); states.emplace_back(); } int get_next(int i, char c) const { while (i != -1 && !states[i].ch.count(c)) i = states[i].link; return i != -1 ? states[i].ch.at(c) : 0; } void build() { std::queue<int> que; que.push(0); while (!que.empty()) { int i = que.front(); que.pop(); for (auto [c, j] : states[i].ch) { states[j].link = get_next(states[i].link, c); states[j].cnt += states[states[j].link].cnt; auto& a = states[j].accept; auto& b = states[states[j].link].accept; std::vector<int> accept; std::ranges::set_union(a, b, std::back_inserter(accept)); a = accept; que.push(j); } } } long long count(const std::string& str) const { long long ret = 0; int i = 0; for (auto c : str) { i = get_next(i, c); ret += states[i].cnt; } return ret; } // list of (id, index) std::vector<std::pair<int, int>> match(const std::string& str) const { std::vector<std::pair<int, int>> ret; int i = 0; for (int k = 0; k < (int)str.size(); ++k) { char c = str[k]; i = get_next(i, c); for (auto id : states[i].accept) { ret.emplace_back(id, k); } } return ret; } }; class DynamicAhoCorasick { std::vector<std::vector<std::string>> dict; std::vector<AhoCorasick> ac; public: void insert(const std::string& s) { int k = 0; while (k < (int)dict.size() && !dict[k].empty()) ++k; if (k == (int)dict.size()) { dict.emplace_back(); ac.emplace_back(); } dict[k].push_back(s); ac[k].insert(s); for (int i = 0; i < k; ++i) { for (auto& t : dict[i]) { ac[k].insert(t); } dict[k].insert(dict[k].end(), dict[i].begin(), dict[i].end()); ac[i].clear(); dict[i].clear(); } ac[k].build(); } long long count(const std::string& str) const { return std::accumulate( ac.begin(), ac.end(), 0LL, [&](auto res, auto& a) { return res + a.count(str); }); } }; #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 "string/pattern_search_2d.hpp" std::vector<std::pair<int, int>> pattern_search_2d( const std::vector<std::string>& txt, const std::vector<std::string>& pat) { AhoCorasick aho; for (int i = 0; i < (int)pat.size(); ++i) { aho.insert(pat[i], i); } aho.build(); std::vector<int> pat_state(pat.size()); for (int i = 0; i < (int)pat.size(); ++i) { pat_state[i] = aho.accept_state[i]; } std::vector txt_state(txt[0].size(), std::vector<int>(txt.size())); for (int i = 0; i < (int)txt.size(); ++i) { int k = 0; for (int j = 0; j < (int)txt[0].size(); ++j) { k = aho.get_next(k, txt[i][j]); txt_state[j][i] = k; } } auto pf = prefix_function(pat_state); std::vector<std::pair<int, int>> res; for (int j = 0; j < (int)txt_state.size(); ++j) { auto match = kmp(txt_state[j], pat_state, pf); for (int i : match) { res.emplace_back(i, j - (int)pat[0].size() + 1); } } return res; } #line 7 "test/aoj/ALDS1_14_C.test.cpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int H, W; cin >> H >> W; vector<string> txt(H); for (auto& x : txt) cin >> x; int R, C; cin >> R >> C; vector<string> pat(R); for (auto& x : pat) cin >> x; auto ans = pattern_search_2d(txt, pat); sort(ans.begin(), ans.end()); for (auto [i, j] : ans) { cout << i << " " << j << "\n"; } }