문자열 검색 알고리즘 찾고자 하는 문자열의 suffix(접두사) 와 prefix(접미사)를 활용해 문자열을 검색한다.

[알고리즘] KMP 알고리즘

왜 사용하는걸까


[출처] 배하람 블로그 https://baeharam.github.io/posts/algorithm/kmp/

[출처] 배하람 블로그 https://baeharam.github.io/posts/algorithm/kmp/

모든 문자열을 탐색할 시 (Brute Force)

알고리즘의 동작방식


🙅‍♂️ 실패함수

만약 ABABAB라는 문자열의 실패함수를 만든다고 하면 아래와 같다

→ 실패함수의 F(k)라고 한다면 k번째 인덱스에서 접두사와 접미사가 일치하는 최대길이를 뜻한다.

결과적으로 실패함수로 0 0 1 2 3 4 라는 결과를 저장한다.

구현 (백준 G4 부분문자열)


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val stdString = br.readLine()
    val pattern = br.readLine()

    print(kmp(stdString, pattern))
}

private fun kmp(standard: String, pattern: String): Int {
    val lpsTable: IntArray = getLpsTable(pattern)
    val standardSize = standard.length
    val patternSize = pattern.length
    var answer = 0

    var j = 0
    for (i in 0 until standardSize) {
        while (j > 0 && standard[i] != pattern[j]) {
            j = lpsTable[j - 1]
        }
        if (standard[i] == pattern[j]) {
            if (j == patternSize - 1) {
                answer = 1
                break
            } else {
                j++
            }
        }
    }

    return answer
}

Failure Function (실패함수)

private fun getLpsTable(string: String): IntArray {
    val patternSize = string.length
    val table = IntArray(patternSize) { 0 }
    var j = 0

		// 0일때는 항상 0이니까 생략해준다.
    for (i in 1 until patternSize) {
        while (j > 0 && string[i] != string[j]) {
            j = table[j - 1]
        }
        if (string[i] == string[j]) {
            table[i] = ++j
        }
    }
    return table
}