[백준] 9250 문자열 집합 판별 +아호코라식 알고리즘

문제

집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하나라도 집합 S에 있으면 'YES'를 출력하고, 아무것도 없으면 'NO'를 출력한다.

예를 들어, 집합 S = {"www","woo","jun"} 일 때, "myungwoo"의 부분 문자열인 "woo" 가 집합 S에 있으므로 답은 'YES'이고, "hongjun"의 부분 문자열 "jun"이 집합 S에 있으므로 답은 'YES'이다. 하지만, "dooho"는 모든 부분 문자열이 집합 S에 없기 때문에 답은 'NO'이다.

입력

첫째 줄에 집합 S의 크기 N이 주어진다. (1 ≤ N ≤ 1000)

다음 N개 줄에 집합 S의 원소들이 주어진다. 이 문자열의 길이는 100을 넘지 않는다.

다음 줄에 답을 판별해야 하는 문자열의 개수 Q가 주어진다. (1 ≤ Q ≤ 1000)

다음 Q개 줄에 답을 판별해야 하는 문자열이 주어진다. 이 문자열의 길이는 10000을 넘지 않는다.

입력으로 주어지는 모든 문자열은 알파벳 소문자로만 이루어져 있다.

출력

Q개 줄에 각 문자열에 대한 답을 출력한다.

 

집합 S의 문자열들이 각각 Q개의 문자열에 존재하는지 확인하는 문제입니다.

문자열 패턴매칭 문제입니다.

만약 집합 S의 문자열들이 아니라, 하나의 문자열이 문자열 안에 존재하는지 확인하는 문제였다면

1대1 패턴매칭으로 KMP알고리즘을 사용하면 됩니다.

 

하지만 이 문제는 집합 S의 여러개의 문자열중 하나라도 있는지 확인하는 다대일 패턴매칭 문제이므로, 

아호코라식 알고리즘을 사용해야합니다.

 

아호코라식 알고리즘은 기본적으로 트라이 구조를 이용합니다.

집합S의 문자열에 대해 트라이를 생성하고, 

문자열의 문자를 순서대로 확인하며 output이 존재하는지 확인하면 됩니다.

 

이때 사용하는 트라이에는 KMP알고리즘처럼 fail함수가 존재합니다.

KMP알고리즘과 마찬가지로 가장 긴 접미사를 찾으면 됩니다.

그 과정은 BFS를 사용합니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

// 트라이 구조체
struct Trie {
    // 현재 노드에서 해당 문자를 받으면 가는 노드
    Trie* go[26];
    // 현재 노드에서 해당 문자의 go 목적지가 없을 때 가는 노드
    Trie* fail;
    // 현재 노드에 도달하면 찾는 문자열 집합: 이 문제에서는 존재성만 따지면 됨
    bool output;

    Trie() {
        fill(go, go + 26, nullptr);
        output = false;
    }
    ~Trie() {
        for (int i = 0; i < 26; i++)
            if (go[i]) delete go[i];
    }
    void insert(string key) {
        if (!key.length()) {
            output = true;
            return;
        }
        int next = key[0] - 'a';
        if (!go[next]) {
            go[next] = new Trie;
        }
        go[next]->insert(key.substr(1));
    }
};
int N, M;
int main() {
    FAST;
    Trie* root = new Trie;
    cin >> N;
    rep(i, N) {
        string str;
        cin >> str;
        root->insert(str);
    }
    queue<Trie*>q;
    root->fail = root;
    q.push(root);
    while (!q.empty()) {
        Trie* cur = q.front();
        q.pop();
        rep(i, 26) {
            if (!cur->go[i])continue;

            Trie* next = cur->go[i];
            //만약 부모노드가 root라면 fail은 root
            if (cur == root)
                next->fail = root;
            else {
                Trie* temp = cur->fail;
                //여기가 어려워
                //만약에 temp가 루트가 아니고, 후보가 존재하지 않는다면 temp는 temp의 fail
                while (temp != root && !temp->go[i])
                    temp = temp->fail;
                //temp가 루트가 아니고 후보가 존재하지 않으면 temp는 temp의 fail
                //만약 temp가 루트거나 후보가 발견되면 반복문을 빠져나옴

                //temp가 루트일수도 있지만, 루트가 아니더라도 만약 후보가 존재하면
                if (temp->go[i])temp = temp->go[i];
                next->fail = temp;
            }
            // fail(x) = y일 때, output(y) ⊂ output(x)
            // 부분에 포함될 수 있음 
            //이게 꼭 필요한가 ? 필요하다
            // 부분에 포함되서 발견해놓고 발견하지 못하는 경우가 생긴다
            // 예를들어 W={a a b c}와 {a b} 같은경우 
            // S="aabc"이면 아무 fail없이 a a b c 로 하나 발견하고 종료된다 따라서 b에서 output=true 처리를 해주어야 a b 발견해서 총 두개발견한다
            if (next->fail->output)
                next->output = true;

            // 큐에 push
            q.push(next);
        }
    }
    cin >> M;
    rep(i, M) {
        string str;
        cin >> str;
        Trie* cur = root; //루트부터 하나씩 비교해볼게요 현재 노드 cur
        bool ans = false;
        for (char c : str) {
            int next = c - 'a'; //현재 단어 next
            //만약 현재 노드가 루트가 아니고, 후보군에 없다면 현재 노드를 실패노드로 변경
            //현재위치가 루트노드가 될 때까지 후보군이 있는지 확인할거임
            while (cur != root && !cur->go[next]) {
                cur = cur->fail;
            }
           
            //만약 후보군이 있다면 움직임
            //후보군이 없다면 현재위치는 루트노드가 될것
            if (cur->go[next])
                cur = cur->go[next];
            //정답이 있다면 출력
            if (cur->output) {
                ans = true;
                break;
            }
            //후보군이 있어서 cur이 이동했을 수도 있지만
            //후보군이 없어서 cur이 이동하지 않았을 수도 있음

        }
        ans ? cout << "YES\n" : cout << "NO\n";
    }
}