KMP 알고리즘
1. KMP(Knuth-Morris-Pratt Alogorithm) 알고리즘이란?
흔히 발견자 Knuth, Morris, Pratt의 앞글자를 딴 KMP로 읽히는 이 알고리즘은 전체 문자열에서 특정 문자열을 찾는 방식으로 오토마타(Finite-state automaton based search) 알고리즘과 비슷한 형식을 가지나 메모리와 시간 양측에서 모두 이득을 볼 수 있어 문자열 검색 알고리즘에서 브루트포스 외에 흔히 사용되는 알고리즘이다.
시간복잡도는 O(N + M)이다.
2. 구현 방식
예를 들어, "ABABABCD" 라는 문자열과 "ABABC"라는 패턴이 존재할 때 KMP 알고리즘으로 문자열을 검색하면 다음과 같은 방식으로 이루어진다.
| A | B | A | B | A | B | C | D |
| A | B | A | B | C | |||
| A | B | A | B | A | B | C | D |
| A | B | A | B | C |
첫 번째로 비교했을때 마지막 문자가 A != C로 틀리게 되었으나, ABAB가 일치하므로 앞의 반복 AB를 뒤의 반복 AB로 가져다놓고 패턴을 다시 비교한다. 즉, 빨간색으로 표시한 일치하는 AB를 놔두고 푸른색 AB를 뒤로 끌어와 매칭시키며 틀렸던 보라색 C를 그 뒤로 빼는 식으로 재배치한다.
이런게 가능한 이유는 탐색 문자열의 앞 부분과 원본 문자열의 뒷부분이 동일하다는 전제 조건 성립하에 문자열 탐색의 중간 불필요한 부분을 건너 뛰는 것이다.
기존에 전부 체크해보던 브루트포스 방식을 사용한다면 위와 같이 인덱스를 1씩 추가해가면서 비교해야하기 때문에 반복문이 3번째 시행되었을 때가 되어야 검색이 완료되었을 것이다. KMP 알고리즘을 사용했을때 위 경우에선 2번째 시행시 완료가 된다. 이는 위와 같은 예제이므로 큰 차이가 안보이지만 문자열이 길어진다면 그 차이는 더욱 크게 드러날 것이다.
3. 동작 순서
이해가 안 갈 수 있기 때문에 동작 순서를 보며 좀 더 자세히 알아보자
위에서처럼 "ABABABCD"라는 문자열이 존재하고, "ABABC"라는 패턴이 존재할 때,
- i와 j를 한 칸 전진시킨 뒤 비교한다.
- i와 j가 매칭되거나 i가 -1일 때 한 칸씩 전진시킨 뒤, j 위치에 i를 저장한다.
- 만약 i와 j가 매칭되지 않는다면 i는 상태전이함수에 있는 값으로 전환시킨 뒤 2번으로 돌아간다.
- j가 n보다 커질 때까지 반복한다.
4. 구현
구현할 때 미리 패턴 내 일치하는 부분을 찾는다.
접두사, 접미사, 경계를 이용해 일치하는 부분을 찾고, 배열을 만들어 저장한다.
| ABABC(패턴 문자열) | |
| 접두사 | 접미사 |
| A | B |
| AB | AB |
| ABA | BAB |
| ABAB | BABC |
여기서 접두사는 왼쪽 문자열, 접미사는 오른쪽 문자열이다.
경계는 접두사와 접미사가 일치할 때, 그 길이를 뜻한다.
경계를 저장할 때, 가장 큰 길이를 저장해둔다. (AB / AB에서 일치하므로 경계는 2)
이제 패턴 내 일치하는 부분을 찾아 배열을 만든 뒤 저장하고 추후 사용한다.
| 일치하는 패턴 문자열 | 접두사 | 접미사 | 경계 길이 |
| A | - | - | 0 |
| AB | A | B | 0 |
| ABA | A, AB | A, BA | 1 |
| ABAB | A, AB, ABA | B, AB, BAB | 2 |
| ABABC | A, AB, ABA, ABAB | C, BC, ABC, BABC | 0 |
배열은 [0, 0, 1, 2, 0]이 된다.
fun makeTable(pattern:String): IntArray {
val patternSize = pattern.length
val table = IntArray(patternSize)
var j = 0
for(i in 1 until patternSize) {
while(j > 0 && pattern[i] != pattern[j]) j = table[j - 1]
if(pattern[i] == pattern[j]) table[i] = ++j
}
return table
}
이후 전체 문자열에서 kmp 알고리즘을 시행한다.
일치했던 패턴의 경계를 이용해 건너 뛰는 방식으로 체크하는 것이다.
건너 뛰는 크기는 일치하는 패턴 길이 - 경계이다.
위에서 구했던 일치하는 패턴의 경계 길이 배열 = [0, 0, 1, 2, 0]
| ↓ ↓ ↓ 배열 인덱스 ↓ ↓ ↓ | |||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| A | B | A | B | A | B | C | D |
| A | B | A | B | C | |||
| 0 | 0 | 1 | 2 | 0 | |||
| ↑ ↑ ↑ 경계 길이 ↑ ↑ ↑ | |||||||
ABAB까진 일치한다. 배열[3] = 2라는 경계를 갖게 된다.
전체 일치하는 패턴 길이 (4) - 경계 (2) = 2이므로 인덱스를 2만큼 이동시킨다.
| A | B | A | B | A | B | C | D |
| A | B | A | B | C |
이동 후, 불일치하는 부분을 다시 체크하면 된다.
fun kmp(parent:String, pattern:String) {
val table = makeTable(pattern)
val parentSize = parent.length
val patternSize = pattern.length
var j = 0
for(i in 0 until parentSize){
while(j > 0 && parent[i] != pattern[j]) {
j = table[j - 1]
}
if(parent[i] == pattern[j]) {
if(j == patternSize - 1) {
println("${i-patternSize+2}에서 찾았습니다.")
j = table[j]
}
else{
j++
}
}
}
}
KMP를 사용하는 메인 함수(또는 다른 함수)에서는 전체 문자열과 패턴문자열을 전달한다.
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main()=with(br){
val parent = "ababacabacaabacaaba"
val pattern = "abacaaba"
KMP(parent, pattern)
bw.flush()
bw.close()
}
5. 구현 전체 코드
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main()=with(br){
val parent = "ababacabacaabacaaba"
val pattern = "abacaaba"
kmp(parent, pattern)
bw.flush()
bw.close()
}
fun makeTable(pattern:String): IntArray {
val patternSize = pattern.length
val table = IntArray(patternSize)
var j = 0
for(i in 1 until patternSize) {
while(j > 0 && pattern[i] != pattern[j]) j = table[j - 1]
if(pattern[i] == pattern[j]) table[i] = ++j
}
return table
}
fun kmp(parent:String, pattern:String) {
val table = makeTable(pattern)
val parentSize = parent.length
val patternSize = pattern.length
var j = 0
for(i in 0 until parentSize){
while(j > 0 && parent[i] != pattern[j]) {
j = table[j - 1]
}
if(parent[i] == pattern[j]) {
if(j == patternSize - 1) {
println("${i-patternSize+2}에서 찾았습니다.")
j = table[j]
}
else{
j++
}
}
}
}