문자열 \(S\)에서 하나의 문자열을 검색하는 것은 간단합니다.
그런데 검색해야 할 문자열이 여러개라면 어떨까요?
일반적인 문자열 탐색 알고리즘으로는 이를 빠르게 처리할 수 없으므로, 다른 방법을 생각해 내야 합니다.
문자열 \(S\)가 있고, 크기가 \(n\)인 문자열의 집합 \(T\)가 있습니다.
\(S\)에서 \(T\)에 속한 문자열 중 적어도 하나를 검색할 수 있는지 여부를 알고 싶습니다.
\(T\)의 크기가 1이라면, 우리는 KMP알고리즘을 이용해 \(O(|S|+|T|)\)에 검색이 가능하다는 것을 알고 있습니다.
KMP
대부분의 문자열 알고리즘은 어떤 문자열이 주어졌을 때, 이 부분 문자열 중 조건에 만족하는 특정한 문자열을 찾는 알고리즘입니다. 가장 단순하게, 문자열 \(S\)에서 문자열 \(T\)를 찾는 방법에
anz1217.tistory.com
\(T\)의 크기가 1이 아니기 때문에 KMP를 그대로 사용할 수는 없지만, KMP의 아이디어는 그대로 이용할 수 있습니다.
문자열 집합 \(T\)에 대한 트라이를 만들어 봅시다.
\(T = \) {"a", "ab", "bab", "bc", "bca", "c", "caa"}
$는 루트노드, 짙은 정점은 해당 노드에 문자열이 존재한다는 표시입니다.
\(S = \) "babca"라고 가정하고, 위의 트라이에서 \(S\)를 검색해 봅시다.
만약 검색하는 도중에 존재하는 문자열이 있다면, 해당 문자열은 \(S\)의 접두사로서 존재한다는 사실을 알 수 있습니다.
일단 \(S\)에 "bab"라는 문자열이 존재함은 확인했는데, 이 다음에는 어떻게 탐색해야 효율적일까요?
KMP에서의 "실패 함수"를 생각해 봅시다.
지금까지 탐색한 문자열 "bab"에서, 접두사와 접미사가 같으면서 최대길이인 부분문자열을 나타내는 트라이의 정점에서 시작해, 탐색을 이어나가면 되지 않을까요?
한번 "bab"에서 접두사와 접미사가 같은 최대길이의 부분문자열은 "b"이므로, "b"를 나타내는 트라이의 정점에서 다시 시작해 탐색을 이어나가 봅시다.
그러면 "bc"와 "bca"도 \(S\)에 존재한다는 사실을 알 수 있게 됩니다.
이런 아이디어로 접근해보면 결국 이 트라이에서, 각 노드에서 탐색을 실패했을 때 탐색을 다시 시작하는 노드(실패 함수)를 잘 찾아 이어주기만 하면 된다는 사실을 알 수 있습니다.
위에서 어떤 노드의 실패 함수를 KMP와 비슷하게,
"지금까지 탐색한 문자열에서, 접두사와 접미사가 같으면서 최대길이인 부분문자열을 나타내는 트라이의 정점"으로 사용했지만,
정확하게는 탐색을 하나의 문자열이 아니라 트라이에서 하고 있기 때문에 실패 함수는
"지금까지 탐색한 문자열에서, 최대 길이의 접미사를 나타내는 트라이의 정점"으로 정의할 수 있습니다.
그러면 각 노드에서의 실패 함수는 어떻게 빠르게 알 수 있을까요?
왼쪽은 문자열 "ba"에 해당하는 노드와, 이 노드의 실패 함수에 해당하는 노드 ("a")를 표시한 그림입니다.
이 정보를 이용하면 "bab"의 실패 함수도 알 수 있지 않을까요?
"ba"의 실패 함수 "a"에서도, 'b'를 추가로 붙인 자식 "ab"가 존재하므로, "bab"의 실패 함수는 "ab"가 됨을 알 수 있습니다.
만약 "a"에서 "ab"가 존재하지 않는다면, KMP에서와 같이 또 "a"의 실패 함수에 해당하는 노드로 이동해 검색하는 것을 반복하면 됩니다.
어떤 노드의 실패 함수는 더 깊이가 작은 노드를 가리키기 때문에, BFS로 트라이를 순회하면서 실패 함수를 계산해주면 됩니다.
위 트라이에서 모든 노드에서의 실패 함수를 표시한 그림입니다. (색깔은 아무 관계 없습니다)
여기에서 끝이라면 정말 좋겠지만, 추가로 한 가지 더 해야 할 작업이 있습니다.
\(S = \) "ba"라고 할 때, 위 트라이를 이용해 문자열 검색을 하면 어떻게 될까요?
"ba"에 해당하는 노드까지 간 다음, 검색된 문자열이 없다고 생각할 수 있지만, 실제로는 "a"라는 문자열이 존재합니다.
트라이에서의 어떤 노드 \(v\)에서, 실패 함수가 가리키는 노드를 \(u\)라고 합시다.
\(u\)가 뜻하는 문자열은 \(v\)가 뜻하는 문자열의 접미사가 될 것입니다.
따라서 만약 \(u\)가 가리키는 문자열이 존재한다면 (짙은 노드라면), \(v\)에서도 문자열이 존재한다고 표시 해주어야 합니다.
주황색 노드들이 이에 해당하는 노드입니다.
트라이의 구축과 BFS의 시간복잡도는 \(O(\sum |T_i|)\),
\(S\)를 트라이에서 검색하는 작업의 시간복잡도는 \(O(|S|)\) 이므로,
총 시간복잡도는 \(O(|S| + \sum |T_i|)\) 입니다.
9250번: 문자열 집합 판별
집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하
www.acmicpc.net
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
struct Node
{
bool exist = 0;
Node* child[26] = { 0, };
Node* fail; // 실패함수가 가리키는 노드
} *Trie;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
Trie = new Node;
cin >> n;
for (int i = 0; i < n; i++)
{
string s; cin >> s;
Node* curNode = Trie;
for (char c : s)
{
int idx = c - 'a';
if (!curNode->child[idx]) curNode->child[idx] = new Node;
curNode = curNode->child[idx];
}
curNode->exist = true;
}
Trie->fail = Trie;
// 루트에서 실패하면 루트로 간다.
queue <Node*> q; q.push(Trie);
while (!q.empty()) // BFS
{
Node* curNode = q.front(); q.pop();
for (int i = 0; i < 26; i++)
{
if (!curNode->child[i]) continue;
Node* curChild = curNode->child[i];
// 자식 노드의 실패함수 계산
Node* failNode = curNode->fail;
if (curNode != Trie)
{
while (failNode != Trie && !failNode->child[i])
failNode = failNode->fail;
if (failNode->child[i]) failNode = failNode->child[i];
}
curChild->fail = failNode;
if (failNode->exist) curChild->exist = true;
// 실패함수에 해당하는 노드에 문자열이 존재하면, 현재 노드에도 문자열이 존재한다.
q.push(curChild);
}
}
int m; cin >> m;
while (m--)
{
string s; cin >> s;
bool ans = false;
Node* curNode = Trie;
for (char c : s)
{
int idx = c - 'a';
while (curNode != Trie && !curNode->child[idx])
curNode = curNode->fail;
if (curNode->child[idx]) curNode = curNode->child[idx];
if (curNode->exist) ans = true;
}
if (ans) cout << "YES\n";
else cout << "NO\n";
}
}
|
제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.
ANZ1217
무슨 내용을 넣어야 좋을까요?
www.acmicpc.net
