Непрерывные фрагменты строки и ограничения

Строку можно исследовать через её непрерывные части: искать участок без запрещённых соседств, считать вхождения шаблона или выделять правильную запись числа. У этих задач общая основа — две границы и точное условие допустимости. Свойства этого условия определяют, какие границы требуется сравнивать, а какие можно исключить без потери ответа.

Позиции и непрерывность

Строка — упорядоченная последовательность символов. Набор разрешённых символов называется алфавитом. Например, строка ABACA использует алфавит ABC. Одинаковые буквы на разных местах остаются разными элементами строки: у каждой своя позиция.

В Python индексы начинаются с нуля. Пусть l — индекс первого символа фрагмента, r — последнего, обе границы включены. Тогда фрагмент содержит все позиции от l до r, а его длина равна r-l+1. В строке ABACA границы 1 и 3 дают BAC длины 3-1+1=3.

Срез Python записывается как s[l:r+1]: верхняя граница среза не входит в результат. Подпоследовательность допускает пропуски, а фрагмент — нет. Поэтому AC является подпоследовательностью строки ABC, но не её непрерывным фрагментом.

Изменяемый фрагмент между двумя границами называют окном.

Вхождение и единица подсчёта

Шаблон — строка, совпадения с которой требуется найти. Вхождение шаблона начинается на определённой позиции и занимает столько соседних символов, сколько содержится в шаблоне. Если его длина равна m, а начало — p, конец находится на позиции p+m-1.

Вхождение входит в окно целиком, только если одновременно выполнены l\le p и p+m-1\le r. В строке ABCA шаблон BC занимает позиции 1 и 2. Окно от 0 до 2 его содержит, окно от 2 до 3 — уже нет: первая буква осталась снаружи.

Вхождения могут перекрываться. В AAAA шаблон AAA встречается два раза: с началами 0 и 1. Вызов s.count("AAA") вернёт один, потому что этот метод считает неперекрывающиеся совпадения. Для общего подсчёта вхождений проверяется каждое возможное начало. У BC самоперекрытия нет, но это свойство конкретного шаблона.

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

Как ограничения меняются вместе с окном

Верхняя квота требует не более заданного числа вхождений. При сжатии окна их количество не увеличивается. Значит, из окна с не более чем двумя буквами A можно удалять края, не нарушая эту квоту. Если букв три, расширение не исправит нарушение: требуется удалить хотя бы одну.

Нижняя квота требует не менее заданного числа вхождений. Она сохраняется при расширении: уже включённые вхождения никуда не исчезают. Но при сжатии нужное вхождение может выйти. В BAAC есть две A; удаление крайних B и C сохраняет это количество, а удаление ещё одной буквы уменьшает его.

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

Эта устойчивость условия при одном направлении изменения называется монотонностью. Она объясняет, почему в некоторых задачах достаточно двух границ, движущихся только вправо. Уже отброшенное начало не станет подходящим после расширения окна, если прежде оно нарушало верхнюю квоту.

Почему минимум и максимум выбирают разные края

Для максимума с верхней квотой при каждом конце нужен самый ранний допустимый старт. Если сдвинуть его дальше вправо, длина уменьшится. Например, в ABCBCCB ровно два BC, но между крайними вхождениями помещается только BCBC длины 4. Для максимума допустимые внешние буквы также нужны: весь фрагмент имеет длину 7.

Для минимума с одной положительной квотой внешние буквы, напротив, можно удалить. Пусть нужны K последовательных вхождений одного шаблона длины m. Первое начинается на p, последнее — на q. Минимальное окно для этой группы начинается на p и заканчивается на q+m-1, поэтому:

(q+m-1)-p+1=q-p+m.

Для двух BC в ABCBCCB получаются p=1, q=3, m=2. Длина равна 3-1+2=4. Сравнение таких групп позволяет найти общий минимум. При дополнительных ограничениях край нельзя удалять автоматически: например, он может содержать другую обязательную букву.

Локальный запрет и обязательная граница

Локальное ограничение проверяется по короткому участку строки. Если запрещено соседство AD, окно, содержащее обе буквы такого вхождения, недопустимо. При фиксированном правом конце убрать нарушение можно сдвигом левого края за A; букву D удалять необязательно.

То же основание работает для запрета XZZY. Если он начинается на позиции p, новое начало должно удовлетворять l\ge p+1. Суффикс ZZY уже не содержит этого вхождения. При нескольких найденных запретах выбирается наиболее строгая из полученных нижних границ. Ранее удалённые символы в окно не возвращаются.

Блоки, числа и правила записи

Подсчёт вхождений отличается от разбиения на целые блоки. В ABCB есть два последовательных двухбуквенных блока: AB и CB. Они не перекрываются и вместе занимают четыре символа. Если блок имеет длину два, число блоков в полном разбиении равно (r-l+1)/2. Начало разбиения имеет значение: сдвиг на один символ меняет пары.

У числа есть правила записи и числовое значение. В одной и той же позиционной системе счисления у записей без ведущих нулей большая длина означает большее неотрицательное число; при равной длине сравнивается первая различающаяся цифра. Нули слева не увеличивают значение: 0012 и 12 обозначают одно число, хотя как строки имеют разную длину.

Грамматика выражения задаёт порядок его частей. Например, число — это 0 либо ненулевая цифра с последующими цифрами; выражение состоит из чисел, разделённых разрешёнными бинарными операциями. Бинарная операция связывает два числа, поэтому знак в начале или конце не подходит.

Строка 10-02*3 нарушает правило числа: 02 начинается с лишнего нуля. Её фрагменты 10-0 и 2*3 записаны правильно. Для такого решения важно помнить, ожидается ли начало числа и допустима ли следующая цифра. Вычисление результата не заменяет проверку записи: 1-2 корректно, хотя значение отрицательно.

От свойств к решению

Как сохранить ровно заданное число вхождений, не перебирая все начала для каждого конца? Почему при поиске минимума границы можно приблизить к крайним нужным вхождениям? Эти переходы применены в статье «Задание №24. Поиск фрагментов строки»: от короткого прохода по буквам до программы для полного входного файла.