KMP Algorithm
KMP 알고리즘
* String Matching Algorithms (문자열 매칭 알고리즘) (URL)
- Knuth, Morris, Pratt이 함께 개발한 String Matching Algorithm이다.
- 메인 문자열 \(\texttt{string[n]}\)에서 특정 패턴\(\texttt{pattern[m]}\)이 존재하는지의 여부를
\(O(n+m)\)에 검색하는 알고리즘이다.
(\(n\) : 메인 문자열의 길이, \(m\) : 검색하고자 하는 패턴 문자열의 길이)
(단순한 Brute-Force Substring Matching 알고리즘은 검색을 \(O(n*m)\)에 수행한다.)
- 오토마타를 이용한 String Matching 알고리즘에서는 Transition Function \(\delta\)를 계산하기 위해
\(\Theta(m * |\Sigma|)\) 개의 Entry를 필요로하는 반면,
KMP 알고리즘에서는 \(\texttt{pattern}\) 문자열의 특성을 보여주는 Array \(\pi\)를 계산하기 위해
단지 \(\Theta(m)\) 개의 Entry만을 필요로 한다.
(즉, \(\delta\) 보다는 \(\pi\)를 계산함으로써 전처리에 소요되는 시간을 \(|\Sigma|\)에 비례하는 값만큼 절약할 수 있다.)
※ 본 포스트에서는 전체 문자열을 \(\texttt{str}\), 검색하고자 하는 부분 문자열을 \(\texttt{pat}\)로 표기한다.
Mechanism (원리)
1. KMP Main Function (\(\texttt{find_kmp()}\))
- 메인 문자열 \(\texttt{str}\)에 부분 문자열 \(\texttt{pat}\)가 존재하는지를 파악하고,
존재한다면, \(\texttt{str}\)에서 \(\texttt{pat}\)가 시작되는 위치를 알린다.
- 먼저 Failure Function을 통해 \(\texttt{pat}\)의 각 인덱스마다
\(\texttt{str}\)과의 Matching 실패 시, Matching을 건너뛰어도 되는 문자의 개수를 계산한다.
(이러한 계산은 \(\texttt{pat}\)에서 Prefix와 Postfix가 일치하는 최대 길이에 대한 계산을 수행한다.)
Example. Failure Value of String \(\texttt{"ABABAB"}\) (\(\texttt{pat = "ABABAB"}\))
Index | Substring | 일치하는 Prefix와 Suffix | F(index) (index에서의 실패함숫값) |
0 | A | - | 0 |
1 | AB | - | 0 |
2 | ABA | A | 1 |
3 | ABAB | AB | 2 |
4 | ABABA | ABA | 3 |
5 | ABABAB | ABAB | 4 |
- 예를 들어, 메인 문자열 \(\texttt{str}\)에서 \(\texttt{"ABABAB"}\)를 검색한다 하자.
만약, \(\texttt{str}\)의 특정 부분에서 \(\texttt{"ABAB"}\)까지만 일치하고 실패했다면,
다음 Matching은 2번 건너 뛴 부분에서 재개하면 된다.
- 이 경우, 건너뛰어도 되는 문자의 개수에 대한 계산은 "여태껏 Matching된 문자의 개수 - 실패 함숫값" 이다.
(2번 건너뛰어도 되는 이유는 4(일치한 문자 4개 = "ABAB") - 2("ABAB" 매칭에 대한 실패함숫값) = 2 이기 때문이다.)
Example. Finding \(\texttt{pat}\) in \(\texttt{str}\) using KMP Algorithm
1) matched != 0 인 상황에서의 불일치 |
![]() |
- 매칭된 문자의 개수가 0이 아닐 경우에서 불일치가 발생한 경우이다. - 이 경우, begin값에 begin + matched - F(index)를 대입하고, matched값에는 F(index)를 대입한 후 다음 루프로 넘어간다. - 여기서 index값은 pat에서 마지막으로 매칭된 문자의 위치값(= matched-1)이다. |
2) matched != 0 인 상황에서의 불일치 |
![]() |
- 매칭된 문자의 개수가 0이 아닐 경우에서 불일치가 발생한 경우이다. - 이 경우, begin값에 begin + matched - F(index)를 대입하고, matched값에는 F(index)를 대입한 후 다음 루프로 넘어간다. - 여기서 index값은 pat에서 마지막으로 매칭된 문자의 위치값(= matched-1)이다. |
3) matched == 0 인 상황에서의 불일치 |
![]() |
- 처음부터 불일치가 발생한 경우이다. - 이 경우, 단순히 begin값을 1만큼 증가시키고 다음 루프로 넘어간다. |
4) matched != 0 인 상황에서의 불일치 |
![]() |
- 매칭된 문자의 개수가 0이 아닐 경우에서 불일치가 발생한 경우이다. - 이 경우, begin값에 begin + matched - F(index)를 대입하고, matched값에는 F(index)를 대입한 후 다음 루프로 넘어간다. - 여기서 index값은 pat에서 마지막으로 매칭된 문자의 위치값(= matched-1)이다. |
5) matched == 0 인 상황에서의 불일치 |
![]() |
- 처음부터 불일치가 발생한 경우이다. - 이 경우, 단순히 begin값을 1만큼 증가시키고 다음 루프로 넘어간다. |
6) matched == pat.size() (str에서 pat를 발견) |
![]() |
- str내에서 pat를 온전히 발견한 경우이다. - 이 경우, begin값에 matched값을 더해서 업데이트한다. |
2. Failure Function (\(\texttt{failure_func()}\))
- 부분 문자열 \(\texttt{pat}\)에서 Prefix와 Postfix가 최대로 일치하는 길이를 계산해주는 함수이다.
- Prefix로서의 \(\texttt{pat}\)과 suffix로서의 \(\texttt{pat}\)로 보고,
Prefix와 일치하는 Suffix가 있는지를 계산한다.
(이 과정 또한, 1번의 KMP Main Function의 알고리즘을 통해 계산된다.)
Example. \(\texttt{pat = "ABABAB"}\)의 각 인덱스 값의 실패 함숫값 계산
1) pat[begin + matched] != pat[matched] |
![]() |
- 이 경우, matched == 0이므로, begin값만 1만큼 증가시킨다. |
2) pat[begin + matched] == pat[matched] |
![]() |
- 이 경우, matched값은 0에서 1이 된다. - matched값을 증가시킨 후(1로 만든 후), 실패 함숫값을 그림과 같이 업데이트한다. |
3) pat[begin + matched] == pat[matched] |
![]() |
- 이 경우, matched값은 1에서 2가 된다. - matched값을 증가시킨 후(2로 만든 후), 실패 함숫값을 그림과 같이 업데이트한다. |
4) pat[begin + matched] == pat[matched] |
![]() |
- 이 경우, matched값은 2에서 3이 된다. - matched값을 증가시킨 후(3로 만든 후), 실패 함숫값을 그림과 같이 업데이트한다. |
5) begin + matched == pat.size() (계산 종료) |
![]() |
- 이 경우, matched값은 3에서 4가 된다. - matched값을 증가시킨 후(3로 만든 후), 실패 함숫값을 그림과 같이 업데이트한다. |
Implementation
* GitHub (URL)
Performance (성능)
Average Time Complexity: \(\Theta(n)\)
(\(n\) is Length of String \(\texttt{str}\))
* Time Complexity of \(\texttt{failure_func()}\): \(\Theta(m)\)
(\(m\) is Length of String \(\texttt{pat}\))
Reference: Introduction to Algorithms 3E
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)
Reference: Fundamentals of Data Structure in C++
(Horowitz, Sahni, Mehta 저, Silicon Press, 2006)
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
Reference: KMP 알고리즘
(배하람 블로그, 2019, URL)
Reference: KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)
(NERO THE CONQUER, 2019, URL)