Да, алгоритм Кнута-Морриса-Пратта (KMP) используется для эффективного поиска подстроки в строке с линейной сложностью.

Основная идея KMP — при несовпадении символов не возвращаться назад по исходной строке, а использовать информацию о уже совпавших префиксах.

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

fun kmpSearch(text: String, pattern: String): List<Int> {
    val lps = IntArray(pattern.length)
    computeLPSArray(pattern, lps)
    val result = mutableListOf<Int>()
    var i = 0 // индекс для text
    var j = 0 // индекс для pattern
    while (i < text.length) {
        if (pattern[j] == text[i]) {
            i++
            j++
        }
        if (j == pattern.length) {
            result.add(i - j)
            j = lps[j - 1]
        } else if (i < text.length && pattern[j] != text[i]) {
            if (j != 0) j = lps[j - 1]
            else i++
        }
    }
    return result
}

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

Этот алгоритм полезен, когда нужно быстро искать множество вхождений подстроки в тексте без повторного сравнения уже проверенных символов.

Имели ли вы опыт использования алгоритма поиска подстрок с помощью метода Knuth-Morris-Pratt (KMP)?