알고리즘/BOJ
[BOJ 9250, C++] 문자열 판별 집합
70825
2022. 9. 4. 22:42
반응형
https://www.acmicpc.net/problem/9250
9250번: 문자열 집합 판별
집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하
www.acmicpc.net
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. 코드
|
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
|
#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;
}
|
cs |
반응형