Как реализовать поиск всех анаграмм подстроки в строке?

Question

Поиск анаграмм реализуется с помощью скользящего окна и частотных таблиц символов. Сначала считается частота символов искомой подстроки, затем окно той же длины «скользит» по строке. При совпадении частот найдено вхождение. Такой алгоритм работает за линейное время.

YeaHub · Accepted Answer

Задача поиска анаграмм — классический пример применения техники sliding window.Что такое анаграмма в этой задачеАнаграмма — это:те же символыв любом порядкес тем же количеством повторенийПорядок символов не важен, важна частота.Наивный подход и его проблемаНаивное решение:брать каждую подстрокусортировать символысравнивать с отсортированным образцомМинусы:сортировка на каждом шагесложность выше линейнойЭффективный подход: sliding windowИдея:Построить частотную карту подстроки patternВести частотную карту текущего окна в строкеСдвигать окно на один символОбновлять частоты, не пересчитывая всё зановоПример базовой логики// частоты pattern и текущего окна сравниваются
// если совпали — найдено вхождение
Важно:длина окна всегда равна длине подстрокидобавляем символ справаубираем символ слеваПочему это эффективнокаждый символ добавляется и удаляется один разнет вложенных цикловсложность O(n)Краткий выводПоиск анаграмм подстроки в строке эффективно решается через скользящее окно и частотные карты. Это позволяет избежать перебора и сортировки.