[BOJ]9250 : 문자열 집합 판별(c++)

[문제] : https://www.acmicpc.net/problem/9250

[풀이]

아호코라식 기초적인 문제이다. 포인터를 쓰지 않고 배열로 구현해 보았다.

[코드]

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;

const int GO_MAX = 26;
const int CHA_MAX = 100001;

struct Trie {
    int cnt;
    int go[CHA_MAX + 1][GO_MAX + 1];
    int output[CHA_MAX + 1];
    int goexist[CHA_MAX + 1];
    int fail[CHA_MAX + 1];

    Trie() {
        cnt = 1;
        memset(go, 0, sizeof go);
        memset(output, 0, sizeof output);
        memset(goexist, 0, sizeof goexist);
        memset(fail, 0, sizeof fail);
    }

    void insert(const char* key, int node = 0)
    {
        if (*key == '\0')
        {
            output[node] = true;
            return;
        }

        int next = *key - 'a';
        if (!go[node][next]) go[node][next] = cnt++;
        goexist[node] = true;
        insert(key + 1, go[node][next]);
    }
};

int main(void)
{
    int N;
    cin >> N;

    Trie trie;

    for (int i = 0; i < N; ++i)
    {
        char ch[101];
        cin >> ch;
        trie.insert(ch);
    }


    queue<int> Que;
    
    trie.fail[0] = 0;

    Que.push(0);

    while (!Que.empty())
    {
        int current = Que.front();
        Que.pop();

        for (int i = 0; i < 26; ++i)
        {
            int next = trie.go[current][i];
            if (!next) continue;


            if (current == 0) trie.fail[current] = 0;
            else
            {
                int dest = trie.fail[current];

                while (dest != 0 && !trie.go[dest][i])
                    dest = trie.fail[dest];

                if (trie.go[dest][i]) dest = trie.go[dest][i];
                trie.fail[next] = dest;
            }

            if (trie.output[trie.fail[next]] == true) trie.output[next] = true;

            Que.push(next);
        }
    }


    bool ZF = false;

    int Q;
    cin >> Q;

    for (int i = 0; i < Q; ++i)
    {
        char ch[10001];
        cin >> ch;
        ZF = false;

        int current = 0;

        for (int j = 0; ch[j]; ++j)
        {
            int next = ch[j] - 'a';

            while (current != 0 && !trie.go[current][next])
                current = trie.fail[current];

            if (trie.go[current][next])
            {
                current = trie.go[current][next];
            }

            if (trie.output[current])
            {
                ZF = true;
                break;
            }
        }

        if (ZF) cout << "YES" << endl;
        else cout << "NO" << endl;

    }

}

지적 환영합니다