[BOJ 9250, C++] 문자열 판별 집합

https://www.acmicpc.net/problem/9250

9250번: 문자열 집합 판별

suffix array가 남았긴한데, 대표적인 문자열 알고리즘인 KMP, Trie, Aho-Corasick을 모두 배웠다.

아호코라식은 Trie 와 KMP를 섞은 일대다 패턴매칭 알고리즘이라고 한다.

결국엔 이것도 Trie를 사용하기 때문에 눈에 익으면 입력값 제한을 확인하여 유형을 찾을만한 알고리즘이라고 생각된다.

 

 

1. 문제 풀이

---

시간복잡도를 계산해보면 각 문자열마다 최대 10,000이고, 집합 S의 문자열의 각 길이는 최대 100에 원소의 개수는 1,000개이므로 아호코라식을 적용하면 O(Q(S + s1 + s2 + ... + sn)) = O(1000 * (10000 + 100000))으로 최소 1억 1천만번의 연산이 필요하다.

 

참고로 KMP 알고리즘을 적용하면 KMP는 일대일 패턴매칭 알고리즘으로 N개의 문자열을 비교해야하므로 O(Q(S*N + s1 + s2 ... + sn)) = O(1000 * (10000 * 1000 + 100000))으로 시간 초과가 나온다..

---

 

 

2. 코드

---

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int n, m;
string s;
 
 
struct Node {
    bool valid = false;
    Node* child[26];
    Node* fail;
 
    Node() {
        fill(child, child + 26, nullptr);
    }
 
    ~Node() {
        for (int i = 0; i < 26; i++) {
            if (child[i]) delete child[i];
        }
    }
 
    void insert(int idx) {
        if (idx == s.size()) {
            valid = true;
            return;
        }
        
        int x = s[idx] - 'a';
        if (!child[x]) {
            child[x] = new Node();
        }
        child[x]->insert(idx + 1);
    }
 
    
};
 
int main() {
    Node* root = new Node();
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        root->insert(0);
    }
 
    queue<Node*> q;
    q.push(root);
    root->fail = root;
 
    while (!q.empty()) {
        Node* x = q.front(); q.pop();
 
        for (int i = 0; i < 26; i++) {
            Node* nx = x->child[i];
            if (!nx) continue;
 
            if (x == root) nx->fail = root;
            else {
                Node* dest = x->fail;
                while (dest != root && !dest->child[i]) dest = dest->fail;
                if (dest->child[i]) dest = dest->child[i];
                nx->fail = dest;
            }
            if (nx->fail->valid) nx->valid = true;
            q.push(nx);
        }
    }
 
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> s;
 
        Node* x = root;
        bool flag = false;
 
        for (int i = 0; i < s.length(); i++) {
            int nx = s[i] - 'a';
            while (x != root && !x->child[nx]) x = x->fail;
            if (x->child[nx]) x = x->child[nx];
            if (x->valid) flag = true;
        }
 
        if (flag) cout << "YES\n";
        else cout << "NO\n";
    }
 
    return 0;
}

---