이 글은 구종만님의 ‘알고리즘 문제해결전략’을 바탕으로 작성하였습니다.
문자열 검색
주어진 긴 문자열 H가 패턴 N을 부분 문자열로 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제를 문자열 검색 문제라고 합니다. H=”starbuckstar”, N=”star” 이라고 하면, H는 N을 두 번 포함하며 각각의 시작 위치는 0, 8 입니다.
이 문제를 푸는 간단한 방법은 N의 가능한 모든 시작 위치를 다 시도해 보는 것입니다. 처음에는 0번 글자에서 시작하는 부분 문자열이 N과 같은지 확인하기 위해 H와 N의 글자를 하나하나 맞춰 나갑니다. 만약 모든 글자가 서로 일치한다면 이 위치를 답에 추가하고, 중간에 실패하거나 답을 하나 찾으면 시작 위치를 오른쪽으로 한 칸 옮겨 계속합니다.
vector<int> naiveSearch(const string& H, const string& N) {
vector<int> ret;
for (int begin = 0; begin + N.size() <= H.size(); ++begin) {
bool matched = true;
for (int i = 0; i < N.size(); ++i) {
if (H[begin + i] != N[i]) {
matched = false;
break;
}
}
if (matched) ret.push_back(begin);
}
return ret;
}
이 알고리즘은 |H|-|N|+1개의 모든 시작 위치에 대해서 비교를 수행합니다. 대개 |H|»|N|이므로 시작 위치의 수는 O(|H|)라고 할 수 있습니다. 각각의 비교에는 O(|N|)의 시간이 걸리기 때문에, 이와 같은 단순한 알고리즘의 전체 시간복잡도는 O(|N|*|H|)이 됩니다.
입력이 큰 경우 이 알고리즘은 꽤 비효율적이지만, 이런 경우는 사실 흔치 않으며 구현이 단순하다는 장점이 있기 때문에 단순한 알고리즘은 표준 라이브러리 구현에 널리 사용됩니다. C의 strstr(), C++ 문자열의 string::find(), 자바 문자열의 indexOf() 등이 모두 이와 같은 알고리즘을 사용합니다.
KMP 알고리즘
일치한 글자의 수는 항상 0에서 |N| 사이의 정수이기 때문에, 전처리 과정에서 이 정보들을 미리 계산해 저장해 둘 수 있습니다. 이와 같은 최적화를 적용한 문자열 검색 알고리즘이 커누스-모리스-프랫(Knuth-Moriss-Paratt) 알고리즘으로, 흔히 KMP 알고리즘이라고 합니다.
KMP 알고리즘을 이해하기 위해 접두사(prefix), 접미사(suffix) 그리고 pi 배열에 대해 알고 있어야 합니다.
-
coffee의 접두사(prefix): c / co / cof / coff / coffe / coffee
-
coffee의 접미사(suffix): e / ee / fee / ffee / offee / coffee
-
pi 배열은 주어진 문자열의 0~i 까지의 부분 문자열 중에서 접미사도 되고 접두사도 되는 문자열의 최대 길이입니다.
| i | 부분 문자열 | prefix=sufix인 문자열 | pi[i] |
| 0 | A | (없음) | 0 |
| 1 | AA | A | 1 |
| 2 | AAB | (없음) | 0 |
| 3 | AABA | A | 1 |
| 4 | AABAA | AA | 2 |
| 5 | AABAAB | AAB | 3 |
| 6 | AABAABA | AABA | 4 |
| 7 | AABAABAC | (없음) | 0 |
vector<int> kmpSearch(const string& H, const string& N) {
int n = H.size(), m = N.size();
vector<int> ret;
vector<int> pi = getPartialMatch(N); // pi[i]=N[..i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이
int begin = 0, matched = 0;
while (begin <= n - m) {
// 만약 짚더미의 해당 글자가 패턴의 해당 글자와 같다면
if (matched < m && H[begin + matched] == N[matched]) {
++matched;
if (matched == m) ret.push_back(begin);
}
else {
// 예외: matched가 0인 경우에는 다음 칸에서부터 계속
if (matched == 0) ++begin;
else {
begin += matched - pi[matched - 1];
// begin을 옮겼다고 처음부터 다시 비교할 필요가 없다.
// 옮긴 후에도 pi[matched - 1]만큼은 항상 일치하기 때문이다.
matched = pi[matched - 1];
}
}
}
return ret;
}
-
begin을 옮길 때 이전에 계산한 pi[] 값을 이용하고 있습니다. 현재 matched 글자가 일치했다면 pi[matched - 1]는 항상 계산된 뒤임을 증명할 수 있기 때문입니다.
-
pi[]의 각 원소는 최대 한 번만 변경되기 때문에 max() 연산을 따로 해 줄 필요가 없습니다.
vector<int> getPartialMatch(const string& N) {
int m = N.size();
vector<int> pi(m, 0);
// KMP로 자기 자신을 찾는다.
// N을 N에서 찾는다. begin=0이면 자기 자신을 찾아버리니까 안됨!
int begin = 1, matched = 0;
while (begin + matched < m) {
if (N[begin + matched] == N[matched]) {
++matched;
pi[begin + matched - 1] = matched;
}
else {
if (matched == 0) ++begin;
else {
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return pi;
}