Поиск подстроки в строке — важная задачка в текстовой обработке. В Go стандартная библиотека имеет strings.Index, но он использует простой перебор символов, который работает с O(n × m) в худшем случае, где n — длина текста, m — длина подстроки.

Алгоритм Кнута-Морриса-Пратта решает эту проблему, используя префикс-функцию, которая позволяет пропускать заведомо ненужные сравнения. В результате его сложность O(n + m), что делает его подходящим для больших текстов и множественных поисковых запросов.

Как работает KMP?

Допустим, ищем "needle" в строке "aaaaaaneedle".

1. Сравниваем "needle" с "aaaaaa", получаем несовпадение.

2. Сдвигаемся на 1 позицию и сравниваем снова.

3. Повторяем процесс, пока не найдем "needle".

В худшем случае O(n × m) операций. Например, поиск "aaaab" в "aaaaaaaaaaaaaaaaaaaaaaaab" будет перебирать почти всю строку.

Алгоритм заранее анализирует паттерн, создавая вспомогательный массив π. Он показывает, насколько далеко можно откатиться назад, чтобы не начинать сравнение заново. Например, при поиске "abcabc" в "abcabcabcabc" не нужно проверять уже известные совпадения.

Построение префикс-функции

Префикс-функция π[i] — это максимальная длина префикса подстроки, который также является ее суффиксом.

Пример для строки "abcaby":

Как строится π?

1. π[0] = 0.

2. Перебираем строку и проверяем, совпадает ли pattern[i] с pattern[j].

3. Если да, увеличиваем j и записываем π[i].

4. Если нет, откатываем j по π[j-1].

Код на Golang:

func computePrefixFunction(pattern string) []int {
    n := len(pattern)
    π := make([]int, n)
    j := 0

    for i := 1; i < n; i++ {
        for j > 0 && pattern[i] != pattern[j] {
            j = π[j-1] // Откатываемся по π
        }
        if pattern[i] == pattern[j] {
            j++
        }
        π[i] = j
    }
    return π
}=

Сложность: O(m).

Поиск подстроки KMP

Используем π для поиска.

func KMPSearch(text, pattern string) []int {
    positions := []int{}
    π := computePrefixFunction(pattern)
    j := 0

    for i := 0; i < len(text); i++ {
        for j > 0 && text[i] != pattern[j] {
            j = π[j-1]
        }
        if text[i] == pattern[j] {
            j++
        }
        if j == len(pattern) {
            positions = append(positions, i-j+1)
            j = π[j-1] // Продолжаем поиск
        }
    }
    return positions
}

К примеру, нужно найти все вхождения "ERROR" в файле логов:

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	file, _ := os.Open("logfile.txt")
	defer file.Close()

	scanner := bufio.NewScanner(file)
	pattern := "ERROR"
	for scanner.Scan() {
		line := scanner.Text()
		if len(KMPSearch(line, pattern)) > 0 {
			fmt.Println(line) // Выводим строки, содержащие "ERROR"
		}
	}
}

π строится за O(m), а поиск выполняется за O(n).

Unicode

Go хранит строки как байтовые слайсы в UTF-8, но KMP работает с символами(рунами).

Пример с Unicode:

package main

import "fmt"

func main() {
    text := "Привет, мир! 你好，世界!"
    runes := []rune(text)
    
    fmt.Println(len(text))  // 27 байт
    fmt.Println(len(runes)) // 15 символов
}

Поэтому KMP должен работать по рунам:

func KMPSearchUnicode(text, pattern string) []int {
    textRunes := []rune(text)
    patternRunes := []rune(pattern)
    positions := []int{}
    π := computePrefixFunction(string(patternRunes))
    j := 0

    for i := 0; i < len(textRunes); i++ {
        for j > 0 && textRunes[i] != patternRunes[j] {
            j = π[j-1]
        }
        if textRunes[i] == patternRunes[j] {
            j++
        }
        if j == len(patternRunes) {
            positions = append(positions, i-j+1)
            j = π[j-1]
        }
    }
    return positions
}

Оптимизация KMP

Как сделать код быстрее?

Используем strings.Index для коротких строк

if len(pattern) < 4 {
    return []int{strings.Index(text, pattern)}
}

Предварительная аллокация массива результатов

positions := make([]int, 0, len(text)/len(pattern))

Уменьшение количества обращений к памяти. Используем байтовые срезы там, где не нужен rune.

Компиляционные оптимизации. Собираем код с -gcflags="-B", убирая лишние проверки компилятора.

KMP — крутая штука, если надо быстро искать подстроки без лишних проверок. KMP полезен для поиска в логах, фильтрации контента и анализа больших файлов. Но если строка часто меняется, лучше смотреть в сторону Aho-Corasick или Suffix Array — всё зависит от задачи.

17 февраля в Otus пройдет открытый урок на тему «Топологическая сортировка вершин в ориентированном графе. Алгоритм Демукрона».

На этом уроке мы поработаем с ориентированным графом. Найти «исток» и «сток» в графе не сложно, а вот как разместить вершины в таком порядке, чтобы все дуги шли в одном направлении, то есть от вершин с меньшим номером к вершинам с большим номером? Такая топологическая сортировка вершин может потребоваться, например, для формирования календаря работ или плана компиляции файлов проекта. Лучше всего с этим справляется алгоритм Демукрона, который мы разберём и реализуем во время вебинара.

Записаться можно на странице курса «Алгоритмы и структуры данных».