BOJ)9250 문자열 집합 판별

문제: icpc.me/9250

n개의 문자열 집합 a와 m개의 문자열 집합 b가 있을 때

b의 원소들을 확인하면서 a의 문자열이 하나라도 부분문자열으로 존재하는지 여부를 출력하는 문제이다.

일대 다 패턴매칭인 아호코라식을 이용하여 해결할 수 있다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct trie {
    trie *go[26];
    trie *fail;
    bool out;
    trie() {
        for (int i = 0; i < 26; i++)
            go[i] = NULL;
        out = false;
    }
    ~trie() {
        for (int i = 0; i < 26; i++)
            if (go[i])delete go[i];
    }
    void insert(const char *key) {
        if (*key == '\0') {
            out = true;
            return;
        }
        int next = *key - 'a';
        if (!go[next])
            go[next] = new trie;
        go[next]->insert(key + 1);
    }
};
bool isexist(char *str, trie *t) {
    trie* here = t;
    for (int i = 0; str[i]; i++) {
        int next = str[i] - 'a';
        while (here != t&&!here->go[next])
            here = here->fail;
        if (here->go[next])
            here = here->go[next];
        if (here->out)
            return true;
    }
    return false;
}
void bfs(trie* root) {
    queue<trie*> qu;
    qu.push(root);
    while (qu.size()) {
        trie *here = qu.front();
        qu.pop();
        for (int i = 0; i < 26; 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;
            }
            if (next->fail->out)next->out = true;
            qu.push(next);
        }
    }
}
int n, m;
char s[10010];
int main() {
    trie* tr = new trie;
    scanf("%d", &n);
    while (n--) {
        scanf("%s", &s);
        tr->insert(s);
    }
    tr->fail = tr;
    bfs(tr);
    scanf("%d", &m);
    while (m--) {
        scanf("%s", &s);
        printf("%s\n", isexist(s, tr) ? "YES" : "NO");
    }
    delete tr;
    return 0;
}