BOJ 10538 빅 피처

BOJ 10538 빅피처

[분류 - 아호코라식]

 

풀이)

  2차원 문자열 매칭이다.
  주어진 hp x wp 크기를 가지는 그림의 행을 패턴으로 보자. 그러면 총 hp개의 패턴이 존재한다. 이 hp개의 패턴을 아호코라식 트라이 A에 저장하자. 각 패턴을 넣을 때 마지막 노드엔 패턴 끝이라는 정보를 행 인덱스로 저장하자. 여기서 이 노드에 행 인덱스가 여러 개 있을 수 있다; 그림에서 i번째 행과 j번째 행이 같다는 소리다. 이건 Union-Find로 합쳐주자.

  이후에 '걸작'을 순회하자. '걸작'의 행들을 각각 탐색 대상 문자열로 보자. 행을 순회할 때마다 방문 노드를 A의 루트로 되돌리며, 매칭되는 패턴을 찾는다. 
  i번째 행 j번째 열을 순회할 때 A에서 어떤 패턴을 찾았다면 이 정보를 2차원 배열 row_dp에 따로 저장한다. 여기서 row_dp에는 Union-Find 때문에 단 하나의 대표 인덱스가 저장된다.

 

row_dp[i][j]=i번째 행 j번째 열을 끝으로하는 패턴의 DSU 상 대표 인덱스. 없다면 -1

  각 행에 대해 비교는 끝났으니 열에 대해 비교할 차례다.
  그림의 각 행을 인덱스를 담는 배열로 변경한다. 단 Union-Find 트리에서 해당하는 대표 인덱스를 가져온다. 가령 그림이 아래와 같다면

oxoo  ooox  xooo  oxoo  oxoo

  결과 배열은 [0, 1, 2, 0, 0] (1, 4, 5 행이 같은 문자열이라 합쳐짐. 물론 인덱스 0이 대표 인덱스가 아닐 수 있다)가 된다.

  이 결과 배열을 아호코라식 트라이 B에 저장한다. 여기서 결과 배열 하나를 패턴으로 본다. 복수 패턴이 아니기 때문에 여기선 KMP를 써도 무방한다.
  다음으로 아까 저장한 row_dp에 대해 이번엔 열을 순회하며 패턴 매칭을 진행한다.

 

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int MAX_N = 2e3, TRIE_SIZE = 8e6;
struct _trie {
    int si = -1, fail;
    vector<pair<int, int>> child;
    bool hasChild(int c) {
        for (auto& chd : child) if (chd.first == c)
            return 1;
        return 0;
    }
    int getIndex(int c) {
        for (int i = 0; i < child.size(); i++) if (child[i].first == c)
            return child[i].second;
        return -1;
    }
};
vector<_trie> trie_row(1), trie_col(1);
int p[MAX_N];
int gv(char c) { return c == 'o'; }
int find(int u) { return u == p[u] ? u : p[u] = find(p[u]); }
void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    p[u] = v;
}
void push(vector<_trie>& trie, int* s, int L, int si) {
    int i, cur = 0;
    for (i = 0; i < L; i++) {
        int& d = s[i];
        if (!trie[cur].hasChild(d)) {
            trie[cur].child.push_back({ d, (int)trie.size() });
            trie.push_back({});
        }
        cur = trie[cur].getIndex(d);
    }
    if (trie[cur].si == -1)
        trie[cur].si = si;
    else merge(trie[cur].si, si);
}
void ahocorasick(vector<_trie>& trie) {
    int i, k, u, v;
    queue<int> q;
    q.push(0);

    while (!q.empty()) {
        u = q.front(), q.pop();
        for (auto& x : trie[u].child) {
            i = x.first;

            _trie& cur = trie[u];
            v = x.second;
            _trie& nxt = trie[v];

            if (!u) nxt.fail = 0;
            else {
                k = cur.fail;
                while (k && !trie[k].hasChild(i))
                    k = trie[k].fail;
                if (trie[k].hasChild(i))
                    k = trie[k].getIndex(i);
                nxt.fail = k;
            }
            if (trie[nxt.fail].si != -1)
                nxt.si = trie[nxt.fail].si;
            q.push(v);
        }
    }
}
int main() {
    char a[MAX_N][MAX_N + 1], b[MAX_N + 1];
    int hp, wp, hm, wm, i, j, k, u, v, row_dp[MAX_N][MAX_N], conv[MAX_N], col[MAX_N], ans = 0;
    scanf("%d%d%d%d\n", &hp, &wp, &hm, &wm);
    for (i = 0; i < hp; i++) {
        scanf("%s", a[i]);
        for (j = 0; j < wp; j++)
            conv[j] = gv(a[i][j]);
        p[i] = i;
        push(trie_row, conv, wp, i);
    }
    for (i = 0; i < hp; i++)
        col[i] = find(i);
    push(trie_col, col, hp, 1);

    ahocorasick(trie_row);
    ahocorasick(trie_col);

    for (i = 0; i < hm; i++) {
        scanf("%s", b);
        for (u = j = 0; j < wm; j++) {
            row_dp[i][j] = -1;

            k = gv(b[j]);
            while (u && !trie_row[u].hasChild(k))
                u = trie_row[u].fail;
            if (trie_row[u].hasChild(k))
                u = trie_row[u].getIndex(k);
            if (trie_row[u].si != -1)
                row_dp[i][j] = find(trie_row[u].si);
        }
    }

    for (i = 0; i < wm; i++) {
        for (u = j = 0; j < hm; j++) {
            k = row_dp[j][i];
            while (u && !trie_col[u].hasChild(k))
                u = trie_col[u].fail;
            if (trie_col[u].hasChild(k))
                u = trie_col[u].getIndex(k);
            if (trie_col[u].si != -1)
                ans++;
        }
    }
    printf("%d", ans);
    return 0;
}