sotanishy's code snippets for competitive programming
#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";
}
}