알고리즘 일지

BOJ 9250 - 문자열 집합 판별 본문

알고리즘 풀이

BOJ 9250 - 문자열 집합 판별

황현석 2024. 1. 11. 15:51

 

 

문제 링크

 
문제 풀이

 
KMP를 이용한 브루트 포스 풀이로, 문제를 제한시간내에 풀지 않았던 문제였다.
클래스 8+가 깨져있길래, 살펴 보았더니, 이 문제의 데이터가 강력하게 업데이트 되어 있었다.
 
그래서 아호코라식을 살짝 보았다. 아호코라식은 자료구조 Trie 에서의 Kmp를 적용하는 것을 말한다.
이미 kmp는 배웠었고, Trie 도 알아서, 그냥 구현했다.
 
아호코라식의 구현은 dfs를 통해 포인터를 리턴하는 것으로 간단하게 하였다.
 
말 그대로 아호코라식을 이용하면, 문자열 집합에서 매칭을 선형으로 탐색할 수 있다.
 
기존풀이는, 문자열 집합 $\textbf{T}$ 에 대해, $\textbf{T}$를 Trie 자료구조를 이용하여, 저장한다음, 매칭 대상 $\textbf{S}$에 대해, $\textbf{S}[0]$ , $\cdots$ , $\textbf{S}[N]$ 까지 문자열을 살펴보며, $\textbf{S}[K]$에서 매칭 실패시, $\textbf{S}[K+1]$ 부터 다시 최대 문자열 100개를 탐색해야하는 풀이었다.
 
그렇게 되면, 한 문자열에서 각 문자마다 100번탐색하게 되니, 최악의 시간 복잡도는 $O(100NQ)$가 되버린다.

내가 가장 고민했던 문제는 Trie의 한 노드에서 FailLink를 찾는데 걸리는 시간복잡도에 있었다.

간단하게 생각해보면, faillink를 찾는데 실패하면 그 노드의 failLink를 타고 failLink를 탐색하게 된다.

이때 부모를 거슬러 올라가므로, 시간은 트리의 깊이에 비례하다는 것을 알 수 있다.

이 문제에서 문자열 집합의 길이는 100이므로 한 노드의 failLink를 찾는데, 최악의 경우 100회밖에 탐색 하지 않는다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
 
using namespace std;
 
struct Trie {
    Trie *leaf[26] = {};
 
    Trie *failLink = 0, *parent = 0;
    bool end = false;
    char type;
 
    Trie (char t, Trie *p) : type(t), parent(p) {}
};
 
void push_backTrie (Trie *node, string &s, int depth) {
    if (s.size() == depth) {
        node->end = true;
        return;
    }
 
    int index = s[depth] - 'a';
 
    if (!node->leaf[index]) {
        node->leaf[index] = new Trie(s[depth], node);
    }
 
    push_backTrie (node->leaf[index], s, depth+1);
}
 
int N, Q;
 
Trie *root = new Trie('!', 0);
 
Trie* findFail (Trie *node, char target) {
    if (!node->leaf[target-'a']) {
        if (node == root) {
            return root;
        } else {
            return findFail(node->failLink, target);
        }
    } else {
        return node->leaf[target-'a'];
    }
}
 
bool findMatch (Trie *node, string &s, int depth) {
    if (node->end) return true;
    if (s.size() == depth) return false;
 
    if (!node->leaf[s[depth]-'a']) {
        if (node == root) return findMatch(node, s, depth+1);
 
        return findMatch(node->failLink, s, depth);
    }
 
    return findMatch(node->leaf[s[depth]-'a'], s, depth+1);
}
 
int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    root->failLink = root;
 
    for (int i=0;i<N;i++) {
        string s;
        cin >> s;
        push_backTrie(root, s, 0);
    }
 
    queue<Trie*> qu;
 
    for (Trie* leafs : root->leaf) if (leafs) {
        qu.push(leafs);
    }
 
 
    while(!qu.empty()) {
        Trie *now = qu.front(); qu.pop();
 
        for (Trie *leafs : now->leaf) if (leafs) {
            qu.push(leafs);
        }
 
        now->failLink = findFail(now->parent->failLink, now->type);
        //예외 처리
        if (now->parent == root) now->failLink = root;
        now->end |= now->failLink->end;
    }
 
 
    cin >> Q;
 
    while(Q-->0) {
        string s;
        cin >> s;
 
        string result = findMatch(root, s, 0) ? "YES\n" : "NO\n";
 
        cout << result;
    }
}
cs

 

'알고리즘 풀이' 카테고리의 다른 글

BOJ 17139 - 초라기와 쿼리  (0) 2024.04.09
BOJ 31226 - 고슴도치 그래프 2  (0) 2024.02.29
BOJ 27989 - 가장 큰 증가하는 부분 수열 2  (0) 2023.05.12
BOJ 27173 - 수열과 쿼리 43  (0) 2023.01.13
BOJ 27114 - 조교의 맹연습 (dx dy 테크닉에 대하여)  (0) 2023.01.09
'알고리즘 풀이' Related Articles more