넘치게 채우기
문자열 패턴 검색: 3 - KMP 알고리즘 본문
설명
Knuth, Morris, Pertt이 만든 문자열 패턴 검색 알고리즘인 KMP 알고리즘은
O(n+m)에 문자열 패턴을 검색해낼 수 있다.
이 알고리즘의 핵심은 lps 배열이다.
lps = Longest Prefix Suffix.
각 위치까지의 부분 문자열에서 자기 자신의 접두사이면서 접미사인 가장 긴 길이를 저장한 배열이다.
패턴 내에서 일치하지 않는 문자가 발견되면, 이전에 계산한 lps를 이용하여 패턴을 적절히 이동한다.
lps[i]는 0부터 i-1까지는
LPS 배열의 생성방법은 다음과 같다:
lps[0]와 len을 0으로 초기화한다. len은 가장 긴 접두사와 접미사 값의 길이이다.
pat[len]과 pat[i]가 일치하면, len을 1 증가하고, 증가된 값을 lps[i]에 할당한다.
일치하지 않고 len이 0이 아니면, len을 lps[len-1]로 업데이트한다.
일치하지 않고 len이 0이면, lps[i]를 0으로 초기화한다.
문자열 "ABABAC"를 예로 들어보자.
lps[0] = 0, len = 0, i = 0으로 시작,
i = 1로 이동.
pat[0] != pat[1]이고, len = 0이므로, lps[1] = 0이다.
i = 2로 이동.
pat[0] == pat[2]이므로, len++, lps[2] = len이다.
len은 1이 되고, lps[2] = 1, i = 3으로 이동.
pat[1] == pat[3]이므로, len++, lps[3] = len이다.
len은 2가 되고, lps[3] = 2, i = 4로 이동.
pat[2] == pat[4]이므로, len++, lps[4] = len이다.
len은 3이 되고, lps[4] = 3, i = 5로 이동.
pat[3] != pat[5]이고, len > 0이므로, len = lps[len-1], lps[5] = 0/
len은 lps[2] = 1이 되고, lps[5] = 0.
KMP 알고리즘의 동작은 다음과 같다:
Naive 알고리즘과는 달리, lps[]의 값을 이용하여 다음에 매치할 문자를 결정할 수 있다.
핵심은 "어차피 매치되는 게 확실한 부분은 매치하지 않는다"이다.
어떻게 lps[]로 다음 위치를 결정하고, 건너뛸 문자 수를 알아내냐면..
- j = 0인 pat[j]와 현재 텍스트 창의 문자와 비교를 시작한다.
- txt[i]와 pat[j] 문자를 계속 일치시키고, 계속 그런 동안 계속 증가시킨다.
- 만약 일치하지 않는다면..
- pat[0...j-1]과 txt[ij...i-1]은 일치한다는 것을 이미 알고 있다.
- 또한, lps[j-1]이 pat[0...j-1]의 접두사와 접미사 모두에 해당하는 문자의 개수라는 것을 알고 있다.
- 결론적으로, lps[j-1]문자를 txt[ij...i-1]과 매치할 필요가 없음을 알 수 있다.
코드(C++)
#include <iostream>
#include <vector>
using namespace std;
void computeLPSArray(string &pat, int M, vector<int> &lps)
{
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0)
{
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
vector<int> KMPSearch(string &pat, string &txt)
{
int M = pat.length();
int N = txt.length();
vector<int> lps(M);
vector<int> result;
computeLPSArray(pat, M, lps);
int i = 0;
int j = 0;
while ((N - i) >= (M - j))
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
result.push_back(i - j + 1);
j = lps[j - 1];
} else if (i < N && pat[j] != txt[i])
{
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
return result;
}
int main()
{
string txt = "hello from the other side hell yeah hello";
string pat = "hell";
vector<int> result = KMPSearch(pat, txt);
for (int i = 0; i < result.size(); i++)
{
cout << result[i] << " ";
}
return 0;
}
복잡도 분석
O(n+m)의 시간복잡도를 갖는다. m은 패턴의 길이, n은 전체 텍스트의 길이이다.
사실상 O(n)이라고 봐도 된다. n > m이기 때문에, O(1.99999.. * n) -> O(n)
공간 복잡도는 O(m) lps배열은 패턴의 길이에 의존한다.
참조
https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
'컴퓨터과학 > 알고리즘' 카테고리의 다른 글
LIS(Longest Increasing Subsequence) - O(nlogn)으로 진짜 LIS를 구하기 (0) | 2024.10.21 |
---|---|
오일러 경로와 오일러 회로(Eulerian Trail, Eulerian Circuit) (0) | 2024.10.16 |
문자열 패턴 검색: 2 - 라빈-카프 알고리즘 (Rabin-Karp Algorithm) (0) | 2024.09.20 |
문자열 패턴 검색: 1 - Naive 패턴 검색 (Naive Pattern Searching) (0) | 2024.09.20 |
[알고리즘] 유니온-파인드(Union-Find) (0) | 2023.09.14 |