Наивный поиск подстроки
Прикладываем образец к каждой позиции и сравниваем буквы — честный O(n·m).
1function naiveSearch(text: string, pattern: string): number[] {2 const found: number[] = []3 4 for (let i = 0; i + pattern.length <= text.length; i++) {5 let j = 06 while (j < pattern.length && text[i + j] === pattern[j]) j++7 if (j === pattern.length) found.push(i)8 }9 10 return found11}Проблема
Прикладываем образец к каждой позиции и сравниваем буквы — честный O(n·m).
Что вы видите
Указатель i бежит по тексту; в каждой позиции — посимвольная сверка с образцом; расхождение гасит попытку.
Как это работает
База для понимания всех поисков: на каждом сдвиге сравнение с нуля. Худший случай даёт O(n·m). KMP и Рабин-Карп лечат именно это.
Пошаговый разбор
- 01
Сдвиг
Образец прикладывается к позиции i.
- 02
Сверка
Буква за буквой до расхождения.
- 03
Дальше
i+1 — всё заново.
Complexity и ограничения
Сложность см. в шапке страницы.
Edge cases
- Пустой вход
Корректная тривиальная обработка.
- Вырожденный случай
Минимум работы — сразу ответ.
Где встречается в реальности
Малые файлы
Для коротких текстов простой цикл быстрее оверхеда умных алгоритмов.
str.includes
Движки браузеров упрощают сканирование на коротких паттернах.
Обучение
Отправная точка перед KMP и Бойером-Муром.
Связанные алгоритмы
«Самый честный поиск подстроки — и почему он медленный»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.