Что такое KMP

KMP (Knuth-Morris-Pratt) — это алгоритм поиска подстроки в строке за линейное время O(n + m). Основная идея — использование префикс-функции для избежания лишних сравнений.

Префикс-функция — массив pi, где pi[i] — длина наибольшего собственного суффикса подстроки s[0..i], совпадающего с её префиксом.

Пример реализации на Kotlin:

fun kmpSearch(text: String, pattern: String): Int {
    val lps = computeLPS(pattern)
    var i = 0
    var j = 0
    while (i < text.length) {
        if (text[i] == pattern[j]) {
            i++
            j++
            if (j == pattern.length) return i - j
        } else {
            if (j != 0) j = lps[j - 1] else i++
        }
    }
    return -1
}

fun computeLPS(pattern: String): IntArray {
    val lps = IntArray(pattern.length)
    var len = 0
    var i = 1
    while (i < pattern.length) {
        if (pattern[i] == pattern[len]) {
            lps[i++] = ++len
        } else {
            if (len != 0) len = lps[len - 1] else lps[i++] = 0
        }
    }
    return lps
}

Используется в текстовых редакторах, поисковых системах и других задачах, где важна эффективность.