Trie и поиск подстроки

Перед началом: деревья (модуль 11), BST (модуль 12), строки (модуль 2). Инструменты: Go 1.27, strings, maps. Трудоёмкость: ~5 ч (теория 2 ч · практика 3 ч).

🔥 Инцидент: «Каждая буква стоила 40 миллисекунд»

В поиске появился автокомплит: на каждый введённый символ сервис показывал подсказки. Реализация была честной — пройти по всем 200 000 запросов словаря и оставить те, что начинаются с префикса. На тестовом словаре в тысячу строк это не замечалось; на проде каждая буква стоила 40 мс, потому что весь словарь просматривался заново на каждый keystroke, а сравнение префикса — это посимвольная работа: O(n · m) на один символ ввода.

Задача решается структурой, где префикс хранится целиком: спуск по дереву символов занимает ровно len(prefix) шагов, а всё поддерево под узлом — уже готовый ответ. В модуле — префиксное дерево (trie), автокомплит за O(длины префикса) и родственная задача: поиск подстроки в тексте за один проход, без откатов (KMP) и через хеши (Rabin-Karp).

📖 Теория

13.1 Trie: дерево символов

Trie (префиксное дерево) хранит строки посимвольно: путь от корня — это префикс, узел — его конец. Словарь {go, gopher, gоть} делит общий путь g → o; после o ветвление: один ребёнок завершает слово, другой ведёт дальше. Ключевое свойство: общая часть строк хранится один раз.

go
type trieNode struct {
	children map[rune]*trieNode // или [26]*trieNode для a-z
	terminal bool               // здесь заканчивается слово
}

type Trie struct{ root *trieNode }

func (t *Trie) Insert(word string) {
	n := t.root
	for _, r := range word {
		next, ok := n.children[r]
		if !ok {
			next = &trieNode{children: map[rune]*trieNode{}}
			n.children[r] = next
		}
		n = next
	}
	n.terminal = true
}

Сложность вставки и поиска — O(m), где m — длина слова: ни количество слов, ни их длины её не меняют. Это главный аргумент против линейного сканирования словаря.

Дети бывают двух видов, и выбор — часть дизайна: map[rune]*trieNode работает с любым алфавитом, но платит за бакеты на каждом узле; [26]*trieNode быстрее и компактнее для латиницы, но фиксирует алфавит и тратит 26 указателей даже на лист. В проде часто берут map для алфавитов вида «всё, что угодно», и массив — для ASCII-идентификаторов.

13.2 Автокомплит: от префикса к ответу

Поиск подсказок — спуск по префиксу, затем обход поддерева: собираем все терминальные узлы ниже. Стоимость — O(m + размер ответа), а не O(словаря).

go
// Complete — все слова словаря с данным префиксом.
func (t *Trie) Complete(prefix string) []string {
	n := t.root
	for _, r := range prefix {
		next, ok := n.children[r]
		if !ok {
			return nil // префикса нет в словаре — ответ пуст
		}
		n = next
	}
	var out []string
	collect(n, prefix, &out)
	return out
}

func collect(n *trieNode, path string, out *[]string) {
	if n.terminal {
		*out = append(*out, path)
	}
	for r, child := range n.children {
		collect(child, path+string(r), out)
	}
}

В реальном автокомплите порядок подсказок задаётся частотой: в терминальные узлы кладут счётчик (или приоритетную очередь top-k на узел — обновление дороже, чтение дешевле). Третий вариант — хранить в каждом узле готовый top-k списка, обновлять его только при вставке в словарь: типичный размен «память на скорость» для горячего пути.

Экономия памяти у зрелых реализаций — сжатие цепочек из одиночных детей (radix tree / Patricia trie): путь «Наполеон» без ветвлений хранится одной строкой, а не 8 узлами. Это то, что используют движки маршрутизации и поиска.

13.3 Поиск подстроки: постановка и наивный метод

Дано: текст t длины n и шаблон p длины m. Найти первое вхождение, все вхождения, или доказать отсутствие. Наивный метод пробует каждую позицию и сравнивает посимвольно — O(n·m) в худшем случае: на тексте aaaa…a и шаблоне aaa…ab почти каждое сравнение доходит до конца и откатывается.

Откат назад — источник квадратичности: после несовпадения наивный метод сдвигает позицию на 1 и перечитывает символы, которые уже проверил.

13.4 KMP: префикс-функция и поиск без откатов

KMP отвечает на вопрос: сколько символов уже проверенного префикса можно переиспользовать после несовпадения? Ответ хранит префикс-функция π: π[i] — длина наибольшего собственного префикса строки p[:i+1], который одновременно является её суффиксом.

go
// prefixFunc: pi[i] = длина наибольшего префикса-суффикса для p[:i+1].
func prefixFunc(p string) []int {
	pi := make([]int, len(p))
	for i, k := 1, 0; i < len(p); i++ {
		for k > 0 && p[i] != p[k] {
			k = pi[k-1] // откат по pi — не по тексту
		}
		if p[i] == p[k] {
			k++
		}
		pi[i] = k
	}
	return pi
}

Поиск идёт один проход по тексту: указатель по тексту никогда не откатывается, при несовпадении откат происходит по шаблону — по π. Суммарно O(n + m): построение π за O(m), проход за O(n).

go
func kmpSearch(text, p string) []int {
	pi := prefixFunc(p)
	var hits []int
	for i, k := 0, 0; i < len(text); i++ {
		for k > 0 && text[i] != p[k] {
			k = pi[k-1]
		}
		if text[i] == p[k] {
			k++
		}
		if k == len(p) {
			hits = append(hits, i-len(p)+1)
			k = pi[k-1] // все вхождения: продолжаем, а не выходим
		}
	}
	return hits
}

13.5 Хеши подстрок: Rabin-Karp

Альтернативный взгляд: сравнивать не символы, а числа. Полиномиальный хеш строки — сумма s[i]·base^(m-1-i) mod M; хеш окна длины m пересчитывается за O(1): убрать старший символ, домножить, добавить новый. Поиск — скользящее окно по хешам, O(n + m) в среднем.

Слабое место — коллизии: разные строки с одинаковым хешем дают ложное срабатывание; поэтому после совпадения хешей делают точное сравнение («проверка кандидата»). Анти-хеш защита: случайный base при старте процесса не даёт злоумышленнику подобрать текст под фиксированный хеш.

Когда что применять:

Z-функция — третий инструмент той же семьи: z[i] — длина общего префикса строки и её суффикса с позиции i. Она даёт те же ответы, что π (часто с более прямым доказательством), и полезна в задачах «найти все вхождения префикса».

13.6 Компромиссы

Ориентир: для одной задачи «найти подстроку» в проде берите strings.Contains/Index. KMP нужен, когда требуются все вхождения за детерминированное O(n+m), когда шаблонов поток и важен худший случай, или когда по условию задачи нельзя терять гарантию времени. Trie — когда ключевая операция «префикс», а не «подстрока».

💻 Практика

1. Trie с полным набором. Реализуйте Insert, Exact (слово в словаре), StartsWith (префикс есть), Complete (все слова с префиксом). Тесты: пустой словарь, слово-префикс другого слова (go и gopher), отсутствующий префикс, юникод-строки.
2. Автокомплит с частотой. Добавьте в терминальные узлы счётчик, наполните словарь датасетом 100 строк, реализуйте Suggest(prefix, k): top-k подсказок по частоте. Оцените, что дешевле — обход всего поддерева с сортировкой или top-k в узле, и при каком k меняется ответ.
3. KMP руками. Реализуйте prefixFunc и kmpSearch. Проверьте на таблице: шаблон в начале, в конце, перекрывающиеся вхождения (aaa в aaaaa), отсутствие. Отдельный тест на π для строки aabaaab.
4. Счётчик сравнений KMP против наивного. На фиксированных данных (текст aaaa…a, шаблон aaa…ab) посчитайте посимвольные сравнения у наивного метода и у KMP. Объясните разницу числом — это и есть цена откатов.
5. Rabin-Karp и проверка кандидата. Реализуйте скользящий хеш, найдите вхождения шаблона в тексте, логируйте число «хеш совпал — строки не совпали» (ложные срабатывания). Прогоните на 100 000 символов: сколько коллизий вышло и почему их не бывает ноль.

🧩 Quiz

✅ Итоги модуля

• Trie хранит строки посимвольно: общий префикс — общий путь; операции за O(m) независимо от размера словаря.
• Автокомплит — спуск по префиксу плюс обход поддерева; частота подсказок хранится в терминальных узлах, top-k — размен памяти на скорость.
• Наивный поиск подстроки квадратичен из-за откатов; KMP откатывает только шаблон по префикс-функции и даёт O(n+m) без перечитывания текста.
• Rabin-Karp сравнивает хеши окон за O(1) на сдвиг, но вероятностен: кандидатов подтверждают точным сравнением, base рандомизируют.
• Инструмент выбирается по задаче: префиксные операции — trie; гарантия времени и все вхождения — KMP; поток и простота — хеши; бытовой случай — strings.Contains.

🔗 Мостик к Модулю 14

Со строками и деревьями разобрались; следующий большой мир — графы: объекты, связанные произвольными связями. В модуле 14 — «Графы: обходы, компоненты, порядок»: представления графа, BFS волнами, DFS с цветами, компоненты и сетка как граф, топологическая сортировка с детектом цикла — те самые обходы, которые дадут порядок выката сервисов и разметят острова.