2020-09-02

KMP 알고리즘

Knuth, Morris, Pratt라는 사람들이 만들어서 앞 글자만 따서 KMP 알고리즘이라 한다. 뭔가 엄청 대충 지은 느낌인데?written by

이거 왜 이렇게 동작할 수 있는거야?

Knuth, Morris, Pratt라는 사람들이 만들어서 앞 글자만 따서 KMP 알고리즘이라 한다. 뭔가 엄청 대충 지은 느낌인데?

아무튼 이 알고리즘은 학부생 때도 짜증 났었는데 지금 봐도 잘 이해가 안 갔었다.
오랜만에 보면 조금 이해하기 어려운 알고리즘인데, 작동하는 원리를 알아야 이해하기도 쉽다.
이해가 된 김에 정리를 잘 해놔야 나중에 보기 편할 거 같아서 포스팅한다.

남이 써놓은 글은 뭔가 내 스타일대로 정리된 글이 아니라서 이해가 안 가기도 하고.

Algorithm

KMP 알고리즘은 접두사(prefix)와 접미사(suffix)가 일치하는 것을 이용한다.

접두사는 문자열의 앞에 나오는 부분 문자열이다.
접미사는 문자열의 뒤에 나오는 부분 문자열이다.
접두사와 접미사는 겹칠 수 있다.

다음 표를 보자.

Partial StringPrefixSuffixTable
Anonenone0
ABnonenone00
ABAAA001
ABABABAB0012
ABABAABAABA00123
ABABABABABABAB001234

ABABAB라는 문자열로 간단하게 접두사와 접미사를 구해놓은 표다.
테이블에는 해당 위치에서 일치하는 접두사와 접미사의 개수를 기록했다.
첫 문자는 비교할 접두사와 접미사가 없으므로 항상 0으로 기록한다.

그럼 접두사와 접미사가 일치하는지를 확인하는 것은 무엇을 의미하는가?

처음에 배우는 단순한 문자열 검색 알고리즘을 생각해보자.

너무 단순하기 때문에 검색하려는 문자열 내에 첫 문자가 중간에 있는지 알기 어렵다.
그래서 검색에 실패하면 첫 문자가 일치하기 시작한 다음 위치로 돌아가는 짓을 해야 한다.

그런데 이 알고리즘은 자연스럽게 검색하는 문자열 내에 시작하는 문자가 있는지를 알 수 있다.

ABBBB라는 문자열을 생각해보자. 테이블은 [0,0,0,0,0]이라는 값을 가지게 된다.
이 테이블은 접두사와 접미사가 하나도 일치하지 않는다는 정보도 있지만...
이 문자열 내에 A로 시작하는 부분이 없다는 것을 나타내기도 한다.
그래서 검색이 실패해도 검색을 시작한 다음 위치로 돌아갈 필요가 없다.

그럼 이 테이블에서 숫자가 의미하는 것은 무엇인가?

검사가 실패하면 실패하기 이전에 그만큼의 문자가 찾으려는 문자열의 시작 부분과 일치한다는 의미다.

사람이 이해하기 쉽게 간단한 예제를 들어보자.

"바나나 먹으면 나한테 바나나 먹으면 나한테 바나나"를 검색해보자.
그리고 마지막 글자에서 검색에 실패했다고 가정하자.
테이블은 [0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]이다.

전체적인 흐름은 다음과 같이 진행된다.

  • 마지막 한 문자가 다르네?
  • 마지막 문자는 다르니까 이전 문자의 테이블을 보니 14다.
  • 그럼 "바나나 먹으면 나한테 바나나 먹으면 나한테 바나나"부터 검사하자.
  • 앞의 "바나나 먹으면 나한테 "라는 문자들은 건너 뛰고 말이지.
  • 그런데 여기서도 일치를 안 하네?
  • 다시 이전 글자의 테이블을 보니 이번엔 2다.
  • 그럼 "바나나 먹으면 나한테 바나나 먹으면 나한테 바나나"부터 검사하자.
  • 또 일치를 안 하네?
  • 이제 '바'로 시작하는 문자가 없으니 '바'로 시작하는 문자가 나올 때까지 검사를 진행하자.

이런 흐름으로 가게 된다.

그래서 중복되는 검사는 최대한 피할 수 있는 것이다.

Kotlin Code

코드를 실행시키면 1, 8, 17, 24가 출력되는 것을 확인할 수 있다.

val pattern = "AB"
val source = "ABC is ABC, and ABD or ABR"

search(source, pattern)

fun makeTable(pattern: String): IntArray {

    // 문자열의 문자 수만큼을 저장해야 하므로 문자열의 길이만큼을 0으로 초기화해준다.
    // 맨 처음 문자는 접두사와 접미사가 없는 것으로 간주하므로 테이블은 반드시 0으로 초기화해야 한다.
    // 그래서 0번 인덱스는 언제나 0이다.
    val table = IntArray(pattern.length) { 0 }

    // j는 현재 접두사와 이전 접미사의 위치를 의미하고, 테이블의 j번 인덱스 값은 그 개수를 의미한다.
    var j = 0

    // 모든 부분 문자열에 대하여 접두사와 접미사를 구하기 위한 반복문
    for (i in 1 until pattern.length) {

        // i와 j가 더 이상 일치하지 않으면 접두사와 접미사가 더 이상 일치하지 않기 때문에
        // 모든 이전 접미사에 대해서도 확인해야 한다.
        // j-1까지는 접두사와 접미사가 일치했기 때문에 이 정보를 이용해보자.
        // 테이블의 j-1 번 인덱스 값은 0번 인덱스부터 j-1 번 인덱스까지
        // 접두사와 접미사가 일치한 개수를 의미한다.
        // 그래서 테이블의 j-1 번 인덱스 값으로 j의 위치를 이동시킨다.
        // 개수는 인덱스보다 1이 크므로 검사할 위치를 나타낸다.
        // 이 과정을 반복하다가 j가 0번 인덱스에 도달하면
        // 이전 접미사가 더 이상 없으므로 루프를 벗어난다.
        while (j > 0 && pattern[i] != pattern[j]) {
            j = table[j - 1]
        }

        // i와 j가 일치하는 시점부터는 접두사와 접미사가 같은 것으로 보고
        // 같은 문자만큼의 개수를 기록한다.
        // j는 인덱스이므로 1을 증가시켜서 기록하자.
        // 개수가 아니라 인덱스로 쓰는 방법도 있지만 테이블을 보기 어렵다.
        // 개수는 인덱스보다 1이 크므로 검사할 위치를 나타낼 수도 있어서 이 방식을 선호한다.
        if (pattern[i] == pattern[j]) {
            table[i] = ++j
        }
    }

    return table
}

fun search(source: String, pattern: String) {

    // KMP 알고리즘을 이용하기 위해서 검색하려는 문자열의 테이블을 생성
    val table = makeTable(pattern)

    // 검사에 필요한 변수
    var j = 0

    // 검색하려는 문자열을 끝까지 검사
    source.forEachIndexed { i, currentChar ->

        // 테이블에서와 똑같이 모든 이전 접미사에 대해서 검사를 진행
        while (j > 0 && currentChar != pattern[j]) {
            j = table[j - 1]
        }

        // 일치하는 문자가 있을 때
        if (currentChar == pattern[j]) {

            // 검색하려는 문자열을 찾았을 때는 해당 위치를 출력하고, 찾지 못하면 검사를 계속 진행
            if (j == pattern.length - 1) {
                println("${i - pattern.length + 2}")
                j = table[j]
            } else {
                j++
            }
        }
    }
}
2020 © Cinntiq's Studio