Современные алгоритмы поиска

Суффиксные автоматы (Suffix Automaton)

Компактная структура, принимающая все суффиксы строки. Размер O(n) узлов (против O(n²) у суффиксного дерева). Строится за O(n).

Применения:

• Поиск всех вхождений подстроки за O(m) после построения.
• Нахождение наибольшей общей подстроки двух строк.
• Подсчёт различных подстрок.

// Концептуальная структура узла
type SAMState struct {
    len  int
    link int
    next map[byte]int
}
// Полная реализация ~50 строк; используется в соревновательном программировании

Нечёткий поиск (Fuzzy Search)

Поиск строк, похожих на шаблон, с учётом допустимого числа отличий.

Основа — расстояние Левенштейна: минимальное число операций (вставка, удаление, замена) для превращения одной строки в другую.

func levenshtein(a, b string) int {
    ra, rb := []rune(a), []rune(b)
    m, n := len(ra), len(rb)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for j := 1; j <= n; j++ { dp[0][j] = j }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if ra[i-1] == rb[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = 1 + min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]))
            }
        }
    }
    return dp[m][n]
}

Для нечёткого поиска по большому словарю используют BK-деревья (Burkhard-Keller): метрическое дерево на основе расстояния Левенштейна.

Постфиксные триггеры (BOT)

Backwards Or-Triggering — битовый алгоритм поиска с ошибками. Кодирует шаблон и текст в битовые маски, применяет битовые операции для одновременной проверки всех позиций. O(n·m/w), где w — ширина машинного слова (64 на современных CPU). Эффективен для коротких шаблонов (m ≤ 64).

Практика в Go

import "strings"

// Простые случаи — стандартная библиотека
strings.Contains(text, pattern)
strings.Index(text, pattern)
strings.Count(text, pattern)

// Регулярные выражения — RE2 (гарантированное O(n·m))
import "regexp"
re := regexp.MustCompile(`go\w+`)
matches := re.FindAllString(text, -1)

Пакет regexp в Go использует алгоритм NFA/DFA (RE2), который гарантирует O(n) по длине текста — в отличие от PCRE, где некоторые паттерны дают экспоненциальный откат.

Упражнения