SeniorКодИногдаЕщё не отвечали
Найти подстроку — перестановку S за O(|T|)
Даны текст T и образец S. Найдите первую подстроку T, которая является анаграммой S (тот же мультимножество символов), и верните её начальный индекс или -1.
Требования:
- O(|T|) по времени с константой, которая НЕ зависит от размера алфавита.
- Окно фиксированной длины
|S|.
int findAnagram(const std::string& T, const std::string& S) {
// ваш код здесь
}Допишите реализацию.
Двигайте окно длины |S| по T и держите один счётчик того, сколько частот символов ещё не совпадают с образцом. На каждом сдвиге добавляйте входящий символ и убирайте выходящий, обновляя счётчик за O(1). Когда он равен нулю — окно анаграмма. O(|T|), независимо от алфавита.
- ✗Перепросматривать весь массив частот на окно, ставя константу в зависимость от размера алфавита
- ✗Забыть и добавить входящий, и убрать выходящий символ на каждом сдвиге
- ✗Путать анаграмму (то же мультимножество) с равенством (тот же порядок)
- →Как вернуть все начальные индексы анаграмм вместо первого?
- →Почему ведение единственного счётчика несовпадений делает работу на сдвиг O(1)?
Оглавление
Задача
Найдите первую подстроку T, являющуюся перестановкой S, за O(|T|).
Решение
#include <string>
#include <array>
int findAnagram(const std::string& T, const std::string& S) {
if (S.size() > T.size()) return -1;
std::array<int, 256> need{}; // нужно символов
int mismatches = 0;
for (unsigned char c : S) { if (need[c]++ == 0) ++mismatches; }
auto add = [&](unsigned char c, int delta) {
if (need[c] == 0) ++mismatches; // было совпадение
need[c] -= delta;
if (need[c] == 0) --mismatches; // стало совпадением
};
for (int i = 0; i < static_cast<int>(T.size()); ++i) {
add(T[i], 1);
if (i >= static_cast<int>(S.size())) add(T[i - S.size()], -1);
if (i >= static_cast<int>(S.size()) - 1 && mismatches == 0)
return i - static_cast<int>(S.size()) + 1;
}
return -1;
}Ключевые моменты
- Окно фиксированной длины
|S|, добавляем входящий и убираем выходящий символ. - Счётчик несовпадений обновляется за O(1), поэтому константа не зависит от алфавита.
- Анаграмма — это совпадение мультимножеств, а не порядка.
Оглавление
