Minimum Window Substring

Зафиксируй начало подстроки. Затем увеличивай её на один символ за раз, подсчитывая количество каждого символа внутри, и после каждого шага проверяй, покрывает ли она t: для каждой из u разных букв, используемых в t, окно должно содержать не меньше экземпляров, чем есть в t. Первый конец, при котором условие выполняется, задаёт самое короткое покрывающее окно с этим началом, поскольку все более короткие варианты с тем же началом уже проверялись и не подошли. На этом остановись.

Повтори это для каждого начала и сохрани самое короткое окно. Начала проверяются слева направо, а окно заменяет лучший результат, только если оно строго короче, поэтому среди окон одинаковой длины остаётся самое левое.

Этот алгоритм работает медленно, когда окна длинные или подходящего окна нет. Если единственная Z в s находится в самом конце, а в t требуется одна такая буква, при каждом начале алгоритм просматривает строку до конца: примерно n²/2 шагов, то есть 1.25 × 10^9 при n = 5 × 10^4, и на каждом шаге выполняет проверку по 52 буквам. То же самое происходит, когда подходящего окна вообще нет.

Два факта позволяют обойтись без перезапуска. Если добавить символы в окно, которое покрывает t, оно продолжит его покрывать; если удалить символы из окна, в котором чего-то не хватает, этого по-прежнему будет не хватать. Поэтому, когда начало сдвигается вправо, конец самого короткого окна, покрывающего t, может либо оставаться на месте, либо сдвигаться вправо. Оба края могут двигаться вперёд одновременно, и ни один из них никогда не движется назад.

Перемещайте right по строке s, добавляя каждый символ в таблицу счётчиков. Когда окно покрывает t, оно становится кандидатом: запишите его, если оно короче лучшего, затем удалите s[left] и сдвиньте left вперёд, после чего проверьте ещё раз. Повторяйте, пока окно не перестанет покрывать t, а затем снова расширяйте его вправо.

Ни одно окно не будет пропущено. Возьмём лучшее окно от L до R. Если бы left прошёл дальше L, прежде чем right достиг R, то какое-то окно от L, заканчивающееся до R, покрывало бы t и было бы короче лучшего. Поэтому, когда right достигает R, цикл сужения передвигает left до L и записывает лучшее окно. Каждый край перемещается не более n раз, но при каждой проверке считывается до u счётчиков — по одному для каждой буквы, используемой в t, — хотя с момента предыдущей проверки изменился только один счётчик.

Оставь то же окно и замени проверку одним числом. Пусть need[c] — это количество вхождений c, которое требуется строке t, минус количество вхождений в окне. Положительное значение означает, что в окне чего-то не хватает, отрицательное — что есть лишние вхождения. Пусть missing — общее количество недостающих вхождений в окне; изначально оно равно длине t. Окно полностью покрывает t, когда missing равно 0.

Обновление занимает один шаг. Когда s[right] входит в окно и значение need для него больше 0, оно заполняет пробел, поэтому missing уменьшается на единицу; в любом случае need уменьшается на единицу и может стать меньше 0, обозначая избыток. Когда s[left] покидает окно, need увеличивается на единицу, и если теперь оно больше 0, окно потеряло вхождение, необходимое строке t, поэтому missing увеличивается на единицу. Избыток появляется и исчезает, не затрагивая missing.

Проследим за s = banana, t = aan: изначально need равно 2 для a и 1 для n, а missing равно 3. b не нужна. Первая a уменьшает missing до 2, n — до 1, вторая a — до 0, поэтому bana покрывает t. Сужение убирает лишнюю b, оставляя ana длиной три символа — это новый лучший результат. Удаление этой a снова устанавливает missing в 1. Последняя a снова обеспечивает покрытие, и окно nana сужается до второй ana. Она не короче, поэтому остаётся самая левая ana.

Каждый символ s один раз входит в окно и не более одного раза покидает его, а каждое перемещение требует фиксированного объёма работы. При построении need строка t просматривается один раз. Весь процесс выполняется за O(n + m), а в качестве единственной дополнительной памяти используется таблица из 128 счётчиков.