BOJ)10256 돌연변이

문제: icpc.me/10256

N^3으로 만들 수 있는 모든 마커를 트라이에 넣어준 뒤 아호코라식을 통하여 몇개의 마커가 주어진 문자열에서 출연하는지 개수를 세주면 되는 문제이다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct trie {
    trie *go[4];
    trie *fail;
    int out;
    trie() {
        for (int i = 0; i < 4; i++)
            go[i] = NULL;
        out = 0;
    }
    ~trie() {
        for (int i = 0; i < 4; i++)
            if (go[i])delete go[i];
    }
    void insert(const char *key) {
        if (*key == '\0') {
            out = 1;
            return;
        }
        int next;
        if (*key == 'A')next = 0;
        else if (*key == 'G')next = 1;
        else if (*key == 'T')next = 2;
        else next = 3;
        if (!go[next])
            go[next] = new trie;
        go[next]->insert(key + 1);
    }
};
int solve(char *str, trie *t) {
    int ret = 0;
    trie* here = t;
    for (int i = 0; str[i]; i++) {
        int next;
        if (str[i] == 'A')next = 0;
        else if (str[i] == 'G')next = 1;
        else if (str[i] == 'T')next = 2;
        else next = 3;
        while (here != t&&!here->go[next])
            here = here->fail;
        if (here->go[next])
            here = here->go[next];
        if (here->out)
            ret += here->out;
    }
    return ret;
}
void bfs(trie* root) {
    queue<trie*> qu;
    qu.push(root);
    while (qu.size()) {
        trie *here = qu.front();
        qu.pop();
        for (int i = 0; i < 4; i++) {
            trie* next = here->go[i];
            if (!next)continue;
            if (here == root)next->fail = root;
            else {
                trie *failure = here->fail;
                while (failure != root&&!failure->go[i])
                    failure = failure->fail;
                if (failure->go[i])failure = failure->go[i];
                next->fail = failure;
            }
            next->out += next->fail->out;
            qu.push(next);
        }
    }
}
int t, n, m;
char s[1000010], v[101];
int main() {
    scanf("%d", &t);
    while (t--) {
        trie* tr = new trie;
        scanf("%d%d", &n, &m);
        scanf("%s %s", &s, &v);
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j <= m; j++) {
                reverse(v + i, v + j);
                tr->insert(v);
                reverse(v + i, v + j);
            }
        }
        bfs(tr);
        printf("%d\n", solve(s, tr));
        delete tr;
    }
    return 0;
}