Как найти все индексы вхождения подстроки с учётом анаграмм?

Question

Для поиска всех индексов используется тот же алгоритм со скользящим окном. При каждом совпадении частот текущего окна с эталоном сохраняется индекс начала окна. В результате возвращается массив всех позиций. Алгоритм остаётся линейным по времени.

YeaHub · Accepted Answer

Поиск индексов — это логическое расширение задачи поиска самих анаграмм.Базовая идеяИспользуется тот же sliding window, но дополнительно:отслеживается текущая позиция окнапри совпадении частот сохраняется индексПоследовательность действийПодготовкачастотная карта подстрокипустой массив результатовИнициализация окнапервые k символов строкиСдвиг окнадобавление нового символаудаление старогоПроверка совпаденияесли карты равны → push(startIndex)Упрощённый пример структурыconst result = []

// при совпадении:
result.push(startIndex)
На что важно обратить вниманиекорректное обновление частот при сдвигеодинаковый размер окнааккуратная работа с символами, частота которых стала нулевойВозможные оптимизациииспользование массивов вместо объектов для ограниченного алфавитасчётчик совпавших символов вместо полного сравнения картКраткий выводВсе индексы анаграмм находятся тем же алгоритмом скользящего окна, что и одиночные вхождения. Разница лишь в накоплении результатов, а асимптотика остаётся линейной.