이번 2학기에 들을 과목들을 살펴보다 알고리즘 교과목 강의계획서를 보니 kmp알고리즘이 있었다. 문자열 매칭을 다룰 때마다 몇 번 듣기는 했었는데 이번 기회에 제대로 공부해보고자 한다.
소스코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector <int> getPi(string);
vector <int> kmp(string, string);
int main() {
string T, P;
getline(cin, T);
getline(cin, P);
vector <int> ans = kmp(T, P);
cout << ans.size() << '\n';
for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
}
vector <int> getPi(string pattern) {
int m = pattern.size();
vector <int> pi(m, 0);
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = pi[j - 1];
}
if (pattern[i] == pattern[j]) {
pi[i] = ++j;
}
}
return pi;
}
vector <int> kmp(string text, string pattern) {
vector <int> ans;
auto pi = getPi(pattern);
int n = text.size(),
m = pattern.size(),
j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j]) {
j = pi[j - 1];
}
if (text[i] == pattern[j]) {
if (j == m - 1) {
ans.push_back(i - m + 1);
j = pi[j];
}
else {
j++;
}
}
}
return ans;
}
0. 사용할 단어
- T : 텍스트. 일치하는 문자열이 있는지 비교 대상이 되는 큰 문자열
- P : 패턴. 텍스트 문자열에서 패턴이 존재하는지 비교할 문자열
- i, j : i 는 텍스트를 순회하는 인덱스 , j는 패턴을 순회하는 인덱스
- n, m : n은 텍스트의 길이, m은 패턴의 길이
1. 시간복잡도
텍스트와 패턴이 있을 때, 텍스트의 모든 문자와 패턴을 비교하도록 반복문을 작성한다면(브루트포스) 텍스트의 길이를 n, 패턴의 길이를 m이라 할 때 O(n * m) 의 시간복잡도를 가진다. T는 aaaaaaaaaa... P는 aaaab 등 일치하는 글자가 잦은 케이스의 문자열을 탐색한다고 하면, 모든 시작위치에서 비교가 이뤄지므로 이러한 특정 조건의 문제에서는 문제가 제시한 시간을 초과할 가능성이 크다. 하지만 kmp알고리즘의 경우 O(n + m) 이라는 시간복잡도를 갖게 된다.
2. 아이디어
위의 예시에 대해 우선 브루트포스 알고리즘이 어떻게 동작하는지 생각해보자. T와 P 를 비교하던 중 i번째 인덱스(색칠된 첫 번째 a를 i 번째 인덱스라 하자) T[i] 와 P[0]가 일치하기 시작하여 이미지와 같이 T[i + 6], P[6] 까지 일치하였고, T[i + 7], P[7] 에서 불일치가 일어났다고 하자. 브루트포스 알고리즘의 경우 T[i + 7], P[7]에서 불일치를 확인한 후 "아, i는 답이 아니군, i + 1 부터 다시 비교를 시작하자" 라고 생각하고 단순히 한 칸을 옮겨 N, begin=i+1 과 같이 취소선이 그어져 있는 인덱스들을 모두 확인할 것이다.
하지만 우리는 i 인덱스에서 (i + 7) 번째 인덱스까지 비교를 진행하는 동안 각 위치에서의 문자를 비교했고, (i + 6) 번째 인덱스까지는 T와 P가 일치한다는 정보를 얻을 수 있다. 이 비교한 정보를 활용하여 조금 더 효율적으로 문자열 비교를 하고자 한다. 이미 비교하며 지나온 정보를 사용하여 정답이 될 수 없는 인덱스는 비교해보지 않고, 정답이 될 가능성이 있는 인덱스만 비교를 진행하는 것이 kmp알고리즘의 핵심 아이디어이다.
즉 정답이 될 수 있는 인덱스만 확인해보기 위해 불일치가 발생하였을 때 인덱스를 어디로 이동한 후 비교를 시작할지 컴퓨터에게 알려줄 방법을 생각해 볼 것이다.
i 에서 (i + 7) 까지 가는 동안 이미지의 색칠된 부분에서도 볼 수 있듯
- T[i + 1]에서 비교할 경우 T[i + 1], P[0] 이 일치한다.
- T[i + 2]에서 비교할 경우 일치하는 부분이 존재하지 않는다.
- T[i + 3]에서 비교할 경우 T[(i + 3) ~ (i + 6)], P[0 ~ 3] 이 일치한다.
- T[i + 4]에서 비교할 경우 T[i + 4], P[0] 이 일치한다.
- T[i + 5]에서 비교할 경우 일치하는 부분이 존재하지 않는다.
- T[i + 6]에서 비교할 경우 T[i + 6], P[0] 이 일치한다.
위와 같은 정보를 찾을 수 있다. 해당 결과를 생각해보자면 2, 5번 정보에 의해 (i + 2), (i + 5) 인덱스에서 시작하는 비교는 절대 답이 될 수 없다는 것을 알 수 있다. 또한 1, 4번 정보의 경우 일치하는 부분이 존재하지만, 일치하는 부분이 T[(i + 6)] 이전에 끝나므로 (결국 일치하지 않는다는 것을 알 수 있으므로) 답이 될 수 없다는 것을 알 수 있다.
마지막으로 3, 6번 정보를 살펴보면 (i + 3) 와 (i + 6) 인덱스에서 비교를 시작하는 케이스의 경우, 현재 인덱스에서 알 수 있는 정보 (i부터 i + 6까지 일치한다는 정보)의 끝까지 모두 일치하므로 (i + 6) 인덱스 이후에도 일치하는지, 일치하지 않는지 확인을 해봐야한다. 즉 '현재로서는 알 수 있는 정보의 끝까지 일치하여, 아직은 모르지만 정답이 될 수 있는 후보' 라는 의미이다. 우린 이것을 컴퓨터에게 다음과 같이 말해줄 수 있다.
"(i + 7)에서 불일치가 일어났지, 그 다음에 어떤 인덱스부터 비교를 해볼지 i ~ (i + 7) 까지 미리 한 번 살펴보고 오니깐 i ~ (i + 7) 중에 T[i + 3] 번째 인덱스에서 시작하는 비교와 T[i + 6]번째 인덱스에서 시작하는 비교는 답이 될 수도 있을것 같아, 한 칸 옮겨서 (i + 1)부터 비교할 게 아니라 (i + 3)과 (i + 6) 으로 가서 끝까지 일치하나 한 번 살펴봐"
위와 같이 비교를 통해 알게된 정보를 다음 비교에 다시 이용하는 것이다. 그렇다면 불일치가 발생했을 때 다시 비교를 시작할 다음 시작 위치를 어떻게 알아야할까에 대해 생각해보자.
3. 다음 시작 위치 찾기
이미지에 기호가 너무 많아 복잡해보이지만 일단 아래 세 가지에 대해서만 생각해보자
- H(짚더미, hatstack) 는 T(text) 를 의미
- N(바늘, niddle) 은 P(pattern) 을 의미
- matched : matched 개의 글자가 일치했다는 뜻. 인덱스로 말하자면 T[i], P[0] 인덱스에서부터 일치가 시작하여 인덱스 T[i + matched - 1], P[matched - 1] 까지 일치한 상태를 의미 (회색으로 칠해진 구간)
T[i] 번째 인덱스부터 비교를 시작하여 T[(i + matched - 1)] 까지 T와 P가 일치한 후 그 다음 인덱스에서 불일치했고, 다음 시작 위치를 정해야할 상황이라고 하자. 이 때 2번 아이디어대로 정답이 될 가능성이 있는 인덱스를 찾아본 결과 임의의 (i + k)번째 인덱스에서부터 비교하는 케이스의 경우 정답이 될 가능성이 있다고 가정하자.
이제 임의로 가정한 수 k를 통해 kmp알고리즘의 동작 방식을 일반화 할 것이다.
블럭 A, B, C 를 보자, 앞서 T[i ~ (i + matched - 1)], P[0 ~ (matched - 1)]이 일치한다고 했으므로 우리가 정한 임의의 k에 대해서 T[(i + k) ~ (i + matched - 1)], P[k ~ (matched - 1)] 즉 블럭 A와 B는 당연히 일치할 것이다.
해당 부분이 조금 난해한데, 블럭 B와 C를 보자. 가정에 의해 (i + k)번째 인덱스에서부터 다시 비교하는 것이 정답이 될 가능성이 있다고 가정했으므로, T[(i + k) ~ (i + matched - 1)] 와 P[0 ~ (matched - 1 - k)]가 일치한다는 뜻이다. (P의 인덱스가 잘 이해되지 않을 수 있는데, T[i] -> T[i + k] 로 이동하여 비교를 시작하고, P도 k만큼 이동한 후 P[0]부터 비교를 시작하면 i 번째 인덱스에 있었을 때의 정보를 통해 T와 P가 일치한다고 알 수 있는 마지막 범위는 위 이미지를 보면 P[0 ~ (matched - 1 - k)]이 된다.) 마지막으로 T[(i + k) ~ (i + matched - 1)], P[0 ~ (matched - 1 - k)]가 일치한다는 뜻은 블럭 B와 C가 일치한다는 뜻이다.
이를 통해 정답일 수 있는 후보인 T[(i + k)]로 이동하여 다시 비교를 시작하게 될 경우 블럭 A, B, C 가 일치해야한다는 것을 알 수 있었으며, 시작위치 T[(i + k)]에서 답을 찾을 수 있기 위해서는 P의 뒷부분인 A와 앞부분인 C가 같아야한다는 것을 알 수 있다. 때문에 '다음 시작 위치'는 P의 각 접미사(P의 뒷부분)에 대해 접두사도 되고, 접미사도 되는 문자열의 최대 길이일 것이라는 결론을 생각해볼 수 있다.
'다음 시작 위치' 인 '어떠한 인덱스에서 접두사도 되고 접미사도 되는 문자열의 최대길이' 를 줄여서 LPS (Longest Prefix Suffix)라고 부르도록 하자. 또한 패턴 문자열 P의 어떠한 인덱스에서, 불일치가 발생했을 때 다시 비교를 시작할 위치인 LPS를 저장하는 배열에 pi[] 라는 이름을 주자.
위 이미지는 P = "aabaabac" 라는 문자열에 대해 pi[] 배열이 어떤 값을 갖게 되는지 보여준 예시이다 (이미지에서의 문자열 N을 우리는 P라고 하자). 예를 들어 P의 현재 인덱스가 4인데 불일치가 발생했다고 하면, P[4]에서의 LPS는 pi[4] = 2 이라는 것을 알 수 있다. 이를 알고리즘에 이용해보자, P[4] 에서 불일치가 발생했다고 할 때 T와 P[4] 에서의 LPS부터 다시 비교를 시작하면 되므로 T와 P[pi[4]] ( = P[2]) 부터 비교를 시작하면 된다. 위의 블럭 개념을 다시 가져와서 인덱스를 하나하나 설명하자면, P[4]에서 불일치가 발생했을 때 P[2], P[3] 이 블럭 A에 해당, P[0], P[1]이 블럭 C에 해당하므로 A, B, C는 이미 일치한다는 것을 알기 때문에 다시 비교를 시작할 때는 B, C 다음블럭인 P[2] 블럭부터 비교를 시작하면 된다.
'불일치가 발생했을 때 P의 해당 인덱스에서의 LPS부터 다시 비교를 시작하면 된다.' 는 결론을 얻었으니, 이제 실제 코드로 어떻게 작성하면 될지 생각해보자.
4. 실제 문자열 검색의 구현
일단은 전처리 과정을 통해 pi[]배열을 계산했다고 하자. 앞에서 숫자를 통해 예를 들었던 것을 문자로 일반화하고자 한다.
다시 해당 그림을 보자. 앞에서 말했던 것처럼 matched 개의 글자가 일치한 후 불일치가 발생했을 때 어느 인덱스부터 비교를 해야할까. T[i + matched], P[matched] 인덱스에서 불일치가 발생하였다면, 앞에서 블록 A, B, C는 같은 문자열임을 알았기 때문에 이제는 B와 C를 다시 비교할 필요 없이 T[(i + matched)] 와 P[(pi(matched - 1))] 부터 다시 비교를 시작하면 된다. (잘 이해가 되지 않는다면 바로 앞에 숫자로 든 예시를 보고 오자)
부연 설명 : T[(i + matched)] 와 P[(pi(matched - 1))]은 이미지에서 B, C 바로 다음 칸을 의미하게 된다. T는 쉽게 알 수 있지만 P의 인덱스를 설명하자면, pi[] 배열은 pi[i] 일 때 P[i] 인덱스에서의 LPS를 의미하고, LPS는 P[i]에서 접두사와 접미사가 일치하는 최대 길이를 의미하므로 P[(pi(matched - 1))] 를 풀어쓰자면 P[(pi(matched - 1))]는 P[matched - 1] 에서 접두사와 접미사가 일치하는 최대 길이. 그 길이를 인덱스로 하는 P이기 때문에, 접두사와 접미사가 일치하는 그 다음 번째 인덱스를 가리키게 될 것이다. 때문에 T[(i + matched)] 와 P[(pi(matched - 1))]은 이미지에서 B, C 바로 다음 칸을 의미하게 된다.
아래는 이를 코드로 구현한 모습이다.
vector <int> kmp(string text, string pattern) {
vector <int> ans;
auto pi = getPi(pattern);
// 일단은 적절한 전처리를 통해 pi배열을 계산했다고 하자.
int n = text.size(),
m = pattern.size(),
j = 0;
// T를 순회하는 인덱스는 i, P를 순회하는 인덱스는 j이다.
for (int i = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j]) {
j = pi[j - 1];
}
// while문이 잘 이해되지 않을 수 있다.
// text[i] != pattern[j] 를 보면 알 수 있듯이 T와 P가 일치하지 않는 케이스를 다루는 부분이다.
// 이 케이스는
// 1. 일치하던 중 불일치 발생.
// 2. 그냥 불일치 중.
// 이렇게 두 가지 케이스로 나눌 수 있으며,
// 그냥 불일치 중일 경우 어떠한 처리도 필요 없이 그냥 다음 T[i]로 넘어가면 되기 때문에
// j > 0 라는 조건을 하나 더 걸어준 것이다.
// T와 P가 일치 중이었다면 P의 인덱스인 j가 j > 0 일테므로,
// (j > 0 && text[i] != pattern[j]) 는 T 와 P가 일치하던 중 불일치가 발생했을 경우 라는 뜻을 가진다.
// 또한 단순히 if문이 아니라 while문인 이유는, T 와 P가 일치하던 중 불일치가 발생했을 경우에
// 인덱스를 j = pi[j - 1] 로 바꿔준 후 즉 P[(pi(matched - 1))] 로 바꾸어 준 후에
// 또 다시 T와 불일치가 발생했을 때 해당 인덱스 j의 자리에서의 LPS가 존재한다면
// 다시 인덱스를 j = pi[j - 1] 로 바꿔준 후 T와 비교를 하겠다는 의미이며,
// j = pi[j - 1] 가 0 이 나와 j == 0 이 된다면, 더 이상 LPS가 없으므로
// "2. 그냥 불일치 중." 케이스에 해당하여 다음 T[i] 로 넘어가게 된다.
if (text[i] == pattern[j]) {
if (j == m - 1) {
ans.push_back(i - m + 1);
j = pi[j];
}
else {
j++;
}
}
}
return ans;
}
5. LPS을 저장하는 pi[] 배열 생성
pi배열을 생성하는 방법은 단순히 P 본인을 여러번 순회하여 LPS를 구하는 등 여러가지 방법이 있을 수 있지만, kmp알고리즘의 동작 원리를 이용하여 pi[] 배열을 생성해보자
vector <int> getPi(string pattern) {
int m = pattern.size();
vector <int> pi(m, 0);
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = pi[j - 1];
}
if (pattern[i] == pattern[j]) {
pi[i] = ++j;
}
// kmp 알고리즘 코드의 경우 T와 P가 일치할 때
// 1. P의 끝까지 다 비교하였다면 해당 비교를 시작한 위치 (i - m + 1)을 저장
// 2. 아직 비교 중이라면 P의 인덱스인 j 를 ++
// 위 두 가지의 조건을 따르지만, pi배열을 구하는 해당 코드의 경우
// 비교하던 P[i]와 P[j]가 일치한다면, 해당 인덱스에서의 문자가 일치한다는 의미이므로
// LPS를 의미하는 pi[i] 의 값을 1 증가한 j로 저장해준다.
}
return pi;
}
'알고리즘 > 공부' 카테고리의 다른 글
| [priority queue] 우선순위 큐 구조체 오름차순 정렬, custom sort (0) | 2021.09.29 |
|---|
댓글