「BeiJing2011」矩阵模板 - AC 自动机

给定一个 行 列的 01 矩阵，以及 个 行 列的 01 矩阵，你需要求出这 个矩阵哪些在原矩阵中出现过。

链接

BZOJ 2462

题解

对模式矩阵的每一行建立 AC 自动机，匹配目标矩阵的每一行。如果目标矩阵的第 行在第 个字符处完成了对模式矩阵的第 行的匹配，则对以 为左上角的子矩阵有 的贡献（表示这个位置的矩阵有一行被匹配了）。

统计答案时，如果某个位置的值 ，则该模式矩阵可以匹配。

代码

#include <cstdio>
#include <cassert>
#include <queue>
#include <utility>

const int MAXN = 1000;
const int CHARSET_SIZE = '1' - '0' + 1;
const int BASE_CHAR = '0';

struct Trie {
    struct Node {
        Node *c[CHARSET_SIZE], *fail, *next;
        bool isWord;
        int id;

        Node(const bool isWord = false, const int id = -1) : fail(NULL), next(NULL), isWord(isWord), id(id) {
            for (int i = 0; i < CHARSET_SIZE; i++) c[i] = NULL;
        }

        void apply(std::vector< std::pair<int, int> > &vec, const int pos) {
            assert(isWord);
            vec.push_back(std::make_pair(pos, id));
            if (next) next->apply(vec, pos);
        }
    } *root;

    Trie() : root(NULL) {}

    template <typename T>
    void insert(const T *begin, const T *end, const int id) {
        Node **v = &root;
        for (const T *p = begin; p != end; p++) {
            if (!*v) *v = new Node();
            v = &(*v)->c[*p];
        }
        if (!*v) *v = new Node(true, id);
        else (*v)->id = id, (*v)->isWord = true;
    }

    void build() {
        std::queue<Node *> q;
        q.push(root);
        root->fail = root;
        root->next = NULL;
        while (!q.empty()) {
            Node *v = q.front();
            q.pop();

            for (int i = 0; i < CHARSET_SIZE; i++) {
                Node *&c = v->c[i];
                if (!c) continue;
                Node *u = v->fail;
                while (u != root && !u->c[i]) u = u->fail;
                c->fail = v != root && u->c[i] ? u->c[i] : root;
                c->next = c->fail->isWord ? c->fail : c->fail->next;
                q.push(c);
            }
        }
    }

    void exec(const bool *begin, const bool *end, std::vector< std::pair<int, int> > &vec) {
        Node *v = root;
        for (const bool *p = begin; p != end; p++) {
            while (v != root && !v->c[*p]) v = v->fail;
            v = v->c[*p] ? v->c[*p] : root;
            if (v->isWord) v->apply(vec, p - begin);
            else if (v->next) v->next->apply(vec, p - begin);
        }
    }

    void clear() {
        root = NULL;
    }
} t;

int main() {
    int n, m, a, b;
    scanf("%d %d %d %d", &n, &m, &a, &b);

    static bool matrix[MAXN][MAXN];
    for (int i = 0; i < n; i++) {
        static char s[MAXN + 1];
        scanf("%s", s);
        for (int j = 0; j < m; j++) matrix[i][j] = s[j] - BASE_CHAR;
    }

    int q;
    scanf("%d", &q);
    while (q--) {
        t.clear();
        for (int i = 0; i < a; i++) {
            static char s[MAXN + 1];
            scanf("%s", s);
            for (int j = 0; j < b; j++) s[j] -= BASE_CHAR;
            t.insert(s, s + b, i);
        }

        t.build();

        static int matchCnt[MAXN][MAXN];
        for (int i = 0; i < n; i++) {
            std::vector< std::pair<int, int> > vec;
            t.exec(matrix[i], matrix[i] + m, vec);
            for (std::vector< std::pair<int, int> >::const_iterator it = vec.begin(); it != vec.end(); it++) {
                 // printf("%d matched %d\n", i, *it);
                if (i - it->second >= 0) matchCnt[i - it->second][it->first - b + 1]++;
            }
        }

        bool flag = false;
        for (int i = 0; i < n; i++) {
            // printf("match(%d) = %d\n", i, matchCnt[i]);
            for (int j = 0; j < m; j++) {
                if (matchCnt[i][j] >= b) flag = true;
                matchCnt[i][j] = 0;
            }
        }

        puts(flag ? "1" : "0");
    }

    return 0;
}