Что такое KMP?

Что такое KMP (Knuth-Morris-Pratt)?

KMP (алгоритм Кнута-Морриса-Пратта) — это один из ключевых эффективных алгоритмов поиска подстроки в строке. Он позволяет найти все вхождения заданного образца (подстроки) в тексте за линейное время, избегая значительного числа повторных сравнений, характерных для наивного алгоритма. В контексте разработки на Android и Kotlin/Java, понимание KMP важно для задач обработки текста, таких как анализ логов, поиск в больших текстовых данных или реализация сложных текстовых фильтров.

Основная идея и проблема наивного поиска

Наивный алгоритм поиска подстроки сравнивает образец с каждым возможным положением в тексте, и в случае несовпадения сдвигает образец всего на одну позицию. Это приводит к временной сложности O(n * m), где n — длина текста, m — длина образца. В худшем случае, например при поиске "aaaab" в "aaaaaaaaab", происходит множество повторных сравнений уже проверенных символов.

KMP решает эту проблему за счет предварительной обработки образца и создания таблицы частичных совпадений (prefix table или lps — longest proper prefix which is also suffix). Эта таблица позволяет при несовпадении сдвигать образец не на один символ, а на большее расстояние, используя уже полученную информацию.

Алгоритм KMP: ключевые этапы

1. Препроцессинг образца (построение таблицы lps).

    Для каждого индекса `i` в образце вычисляется длина наибольшего собственного префикса, который одновременно является суффиксом для подстроки `pattern[0..i]`. Это позволяет знать, какая часть образца уже совпала, даже при несовпадении текущего символа.

    **Пример построения lps для образца "ABABACA":**

    | Индекс | Подстрока | LPS значение | Причина                                 |
    |--------|-----------|--------------|-----------------------------------------|
    | 0      | A         | 0            | Нет префикса-суффикса                   |
    | 1      | AB        | 0            | "A" != "B"                              |
    | 2      | ABA       | 1            | Префикс "A" = суффикс "A"               |
    | 3      | ABAB      | 2            | Префикс "AB" = суффикс "AB"             |
    | 4      | ABABA     | 3            | Префикс "ABA" = суффикс "ABA"           |
    | 5      | ABABAC    | 0            | Нет совпадения                          |
    | 6      | ABABACA   | 1            | Префикс "A" = суффикс "A"               |

1. Поиск подстроки с использованием таблицы lps.

    Алгоритм проходит по тексту, сравнивая символы текста и образца. При совпадении индексы обоих увеличиваются. При несовпадении, вместо сдвига на один символ в тексте и возврата к началу образца, индекс образца сдвигается на значение из таблицы `lps` для предыдущего символа образца. Это позволяет продолжить сравнение с уже частично совпавшей частью.

Реализация в Kotlin для Android-разработчика

Вот пример реализации KMP на Kotlin, который может быть использован в Android проекте для поиска в тексте:

fun searchSubstringKMP(text: String, pattern: String): List<Int> {
    val result = mutableListOf<Int>()
    val n = text.length
    val m = pattern.length

    // 1. Строим таблицу LPS (Longest Prefix Suffix)
    val lps = computeLPSArray(pattern)

    var i = 0 // индекс для текста
    var j = 0 // индекс для образца

    while (i < n) {
        if (pattern[j] == text[i]) {
            i++
            j++
        }
        if (j == m) {
            // Найдено полное совпадение
            result.add(i - j)
            j = lps[j - 1] // продолжаем поиск следующего вхождения
        } else if (i < n && pattern[j] != text[i]) {
            // Несовпадение
            if (j != 0) {
                j = lps[j - 1] // используем таблицу для сдвига образца
            } else {
                i++ // сдвигаем текст, если j == 0
            }
        }
    }
    return result
}

fun computeLPSArray(pattern: String): IntArray {
    val m = pattern.length
    val lps = IntArray(m)
    var length = 0 // длина предыдущего префикса-суффикса
    var i = 1

    while (i < m) {
        if (pattern[i] == pattern[length]) {
            length++
            lps[i] = length
            i++
        } else {
            if (length != 0) {
                length = lps[length - 1] // откатываемся, используя уже вычисленные значения
            } else {
                lps[i] = 0
                i++
            }
        }
    }
    return lps
}

// Пример использования в Android (например, в лог-анализе)
fun exampleUsage() {
    val logText = "Error: DBConnectionFailed; Info: UserLoggedIn; Error: NetworkTimeout"
    val searchPattern = "Error"
    val positions = searchSubstringKMP(logText, searchPattern)
    println("Позиции вхождения '$searchPattern': $positions")
    // Вывод: Позиции вхождения 'Error': [0, dd1] (с учетом длины "Error: ")
}

Преимущества KMP в разработке Android

• Линейная временная сложность: O(n + m), что критично для обработки длинных строк (например, содержимое файлов, JSON ответы от API) в мобильном приложении без задержек UI.
• Эффективность при повторных сравнениях: Особенно полезен при поиске образцов с повторяющимися символами, которые часто встречаются в данных.
• Основа для других алгоритмов: Понимание KMP помогает освоить более сложные алгоритмы, например, Aho-Corasick для поиска множества подстрок одновременно.

Практическое применение в Android

• Поиск в локальных базах данных или файлах: Когда необходимо быстро найти ключевые слова в больших текстах без использования внешних библиотек.
• Реализация текстовых фильтров или выделения: Например, выделение всех ссылок или определенных тегов в тексте комментария.
• Анализ логов приложения: Поиск конкретных ошибок или событий в потоке логов для формирования отчетов.
• Обработка введенного пользователем текста: Поиск шаблонов или запрещенных слов в реальном времени (с учетом эффективности).

Таким образом, KMP — это не просто академический алгоритм, а практический инструмент для оптимизации задач поиска в тексте, который может повысить производительность вашего Android приложения при работе со строковыми данными.