sotanishy's competitive programming library

sotanishy's code snippets for competitive programming

View the Project on GitHub sotanishy/cp-library-cpp

:heavy_check_mark: test/aoj/ALDS1_14_C.test.cpp

Depends on

Code

#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";
    }
}
Back to top page