Задание №24. Поиск фрагментов строки

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

Фрагмент и его границы

Непрерывный фрагмент содержит все символы между выбранными границами, без пропусков. В строке ABC есть фрагмент BC, но нет фрагмента AC. Пусть исходная строка хранится в переменной s, индекс первого выбранного символа равен l, последнего — r. Индексы отсчитываются от нуля, обе границы включены.

В Python этот фрагмент записывается как s[l:r+1]: правая граница среза не включается, поэтому к индексу последнего символа прибавляется единица. Длина фрагмента равна r-l+1. Например, в ABCB границы l=1 и r=2 выделяют BC длины 2-1+1=2.

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

Максимальная длина при точном количестве BC

В задании с ровно 190 вхождениями BC ↗ требуется максимальная длина фрагмента. Из приложения 88B226.zip используется файл 88B226.txt. В нём одна строка из 10 миллионов букв; ответ измеряется в символах, а ограничение — в двухбуквенных вхождениях BC.

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

1. Правая граница сдвигается на один символ. Новое BC может только закончиться на этом символе, поэтому достаточно проверить последние две буквы. При совпадении счётчик увеличивается на один.
2. Если вхождений стало больше 190, окно недопустимо. Левая граница движется вправо; перед удалением символа проверяется, начинается ли на нём BC. Если да, это вхождение выходит из окна и счётчик уменьшается. Сжатие продолжается, пока лишнее вхождение не исчезнет.
3. Теперь вхождений не более 190. При точном равенстве длина r-l+1 сравнивается с лучшей найденной. При меньшем количестве ответ не обновляется: условие ещё не выполнено.

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

Как меняется короткое окно

Для ручной иллюстрации используется учебная строка ABCBCCBCF и уменьшенный порог: ровно 2 вхождения BC. Это другие данные; в настоящем задании порог остаётся 190. Первые буквы B нужных пар имеют индексы 1, 3 и 6.

При r=2 завершается первое BC, при r=4 — второе. К r=5 в окне уже две пары, а последняя C счётчик не меняет.

При конце 6 новая B ещё не завершает пару: вхождений по-прежнему два. При конце 7 добавляется C, и в исходном окне ABCBCCBC пар становится три. Удаление начальной A ничего не меняет. Следом удаляется B с индексом 1: первое BC перестаёт входить целиком, счётчик возвращается к двум. Новое начало l=2 даёт длину 7-2+1=6. Последняя F увеличивает длину до 7 без изменения счётчика.

Изменения l, r, count и best на каждом шаге показаны в статье «Как работает программа поиска окна». Отдельно прослежены два удаления слева при появлении лишней пары.

Программа для полного файла

Файл после распаковки находится в рабочей папке программы. readline() читает его единственную строку, а strip() убирает завершающий перевод строки. Такой способ чтения подходит этому вложению; для файла из нескольких значимых строк способ чтения определялся бы отдельно.

Переменные l и r задают включённые границы, count хранит число целых BC, best — максимальную найденную длину. Переменная pair нужна для проверки двух соседних букв. До второго символа пара не проверяется: при r == 0 предыдущей буквы нет.

with open("88B226.txt") as f:
    s = f.readline().strip()

l = 0
count = 0
best = 0
for r in range(len(s)):
    if r > 0:
        pair = s[r-1:r+1]
        if pair == "BC":
            count += 1
    while count > 190:
        pair = s[l:l+2]
        if pair == "BC":
            count -= 1
        l += 1
    if count == 190:
        size = r-l+1
        best = max(
            best, size
        )
print(best)

Цикл for перебирает все индексы строки, включая последний. Цикл while удаляет столько символов слева, сколько необходимо для возврата к верхнему ограничению. Проверка пары выполняется перед увеличением l, иначе было бы потеряно место начала удаляемого вхождения. max сохраняет большее из прежнего результата и текущей длины.

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

Ответ и проверка границ

На полном входном файле программа печатает 2287. Один из максимальных фрагментов начинается с индекса 8 423 821 и заканчивается индексом 8 426 107 включительно. Его длина:

8\,426\,107-8\,423\,821+1=2287.

Внутри ровно 190 вхождений BC. Предыдущее начинается на позиции 8 423 820: его B уже снаружи. Следующее начинается на позиции 8 426 107: его B ещё включена, но C на позиции 8 426 108 остаётся за правой границей. Это объясняет, почему фрагмент может начинаться с C и заканчиваться на B, не добавляя лишних целых пар.

Что меняется в других условиях

Не более, не менее и минимум

Для максимума с условием \le K, где K — разрешённое количество вхождений, после удаления лишних обновляется ответ без проверки равенства. Так устроено условие о не более 110 вхождениях AB ↗. Для максимума с точной квотой остаётся отдельная проверка =K, как в основном примере.

Для минимума направление выбора другое: после выполнения нижнего ограничения окно сжимается, пока его ещё можно сократить. Кандидат записывается до удаления символа, которое нарушит условие. В задаче о не менее 240 буквах W ↗ лишнюю крайнюю W можно удалить вместе с ненужным краем. Поэтому кратчайший вариант содержит ровно 240 таких букв. Это следствие одной квоты; при нескольких ограничениях удаление может нарушить другое.

Для одного шаблона есть короткая альтернатива: сохранить позиции начал его вхождений. Если длина шаблона равна m, а начала первого и последнего из нужных K подряд идущих вхождений равны p и q, кратчайшее окно имеет длину q-p+m. Оно начинается на первом символе первого вхождения и заканчивается на последнем символе последнего. Для минимума с ровно 220 вхождениями AB ↗ сравниваются такие группы по 220 начал, а m=2. Расширять края, как при максимуме, здесь незачем.

Несколько счётчиков, заданное начало и конец

Каждое самостоятельное требование сохраняется при выборе кандидата. В максимуме с ровно 80 буквами Y и не менее 90 подстроками 2025 ↗ нужны два счётчика. Верхняя квота по Y определяет сжатие; после него проверяются и равенство по Y, и нижняя квота по 2025. Если самого длинного окна с данным концом не хватает по нижней квоте, более короткое тоже не поможет.

В условии с окончанием 2025 ↗ требуется ровно 50 вхождений 2025 и не менее 140 букв Y. Сжатие ограничивает число 2025, но кандидат рассматривается только на конце целого 2025 и при выполнении обеих квот. Подстрока длины четыре добавляется в счётчик лишь после появления четвёртого символа; при удалении её первого символа вхождение вычитается.

В минимуме с ровно 90 буквами W и не менее 110 подстроками 2025 ↗ после удаления избытка W допустимый фрагмент дополнительно сжимается. Сокращение продолжается, пока сохраняются оба требования. Кратчайший вариант может содержать больше 110 вхождений 2025: удаление ещё одного способно убрать необходимую W.

Заданное начало нельзя заменить произвольной левой границей. В задаче о старте с чётной цифры и ровно 30 буквах W ↗ начало фиксируется на чётной цифре, а следующая чётная цифра уже не входит в фрагмент. Между этими границами остаётся выбрать конец с нужной квотой. Аналогично отдельно учитываются начало с N и подсчёт цифр ↗ и начало с G и подсчёт нечётных цифр ↗.

Запрещённые соседства и шаблоны

В условии с чередованием букв и цифр ↗ сравниваются категории соседних символов. Две буквы или две цифры подряд нарушают условие; левая граница переносится на второй символ такой пары. Здесь учитывается длина в символах: неполную пару на краю отбрасывать не требуется.

Здесь нарушение само задаёт необходимый сдвиг. Если запрещённая пара занимает позиции r-1,r, новое начало должно быть не раньше r: первая буква пары исключается. В условии без соседства A и D ↗ проверяются обе пары AD и DA, но AA и DD разрешены.

Для более длинного запрета достаточно исключить первый символ найденного вхождения. Если XZZY начинается на позиции p, левая граница становится не меньше p+1. Суффикс ZZY остаётся: он сам по себе не нарушает запрет XZZY ↗. Если другие ограничения уже сдвинули начало дальше, назад оно не возвращается.

Последовательности целых пар

В задаче о парах «согласная + гласная» ↗ фрагмент состоит из неперекрывающихся блоков длины два. После принятой пары следующая начинается через две позиции. Возможны начала как на чётном, так и на нечётном индексе, поэтому проверяются оба выравнивания. Неподходящий блок завершает текущую цепочку; её длина измеряется в парах, то есть равна половине числа символов.

В условии с парами AB или CB ↗ пары разрешено чередовать: ABCB содержит два подходящих блока. Нельзя искать только повторения одной выбранной пары. Набор гласных и согласных берётся из конкретного условия; например, оговорка к файлу с буквами A, C, D, E, F ↗ задаёт гласные AE и согласные CDF.

Число в основании 14

В поиске максимального чётного 14-ричного числа ↗ сначала выделяются непрерывные участки из 0123456789ABCD. Буквы A, B, C, D означают цифры 10, 11, 12, 13. Поскольку основание чётное, чётность числа определяется последней цифрой: подходят 02468AC.

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

Корректная запись выражения

В задаче о правильном арифметическом выражении ↗ допустимость определяется порядком чисел и операций. Число записывается как 0 либо начинается с ненулевой цифры; затем могут идти другие цифры. Между двумя числами стоит ровно один разрешённый знак операции. Знак в начале или конце, два знака подряд и число с ведущим нулём не подходят.

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

Вычислять значение с помощью eval не требуется: ищется длина правильной записи. Бинарный минус стоит между числами, а не обозначает отрицательный операнд. При этом значение всего выражения может быть отрицательным: 1-2 записано правильно.

Возможные ловушки

• Посчитать отдельные B и C вместо BC. В задаче с квотой 190 ↗ считаются совпадения двух соседних букв, целиком внутри окна. Проверка count <= 190 гарантирует лишь верхнюю квоту и допускает окна с недостаточным числом пар. Проверка count == 190 явно сохраняет точное условие каждого учитываемого кандидата.
• Сохранить только одну из квот. В условии с концом 2025 ↗ проверка ровно 50 вхождений ещё не гарантирует ни 140 букв Y, ни нужное окончание. Все три требования проверяются у одного и того же окна.
• Удалить весь запрещённый шаблон. После вхождения XZZY ↗ сдвиг за последнюю Y теряет разрешённое начало ZZY и может уменьшить максимум. Достаточно сдвига за первую X.
• Расширить или сузить запрет по названию букв. В запрете соседних букв из набора ABC с повторениями ↗ запрещены также AA, BB и CC. В запрете соседства A и D ↗ повторения, напротив, допустимы. Проверяется точный набор запрещённых пар.
• Считать перекрывающиеся пары или вернуть число символов. В цепочке AB/CB ↗ следующий блок начинается через два символа, а ответ выражен в блоках. Переход через один символ меняет разбиение; отсутствие деления длины на два удваивает ответ.
• Принять A за нечётную цифру или включить ведущие нули. В 14-ричной записи ↗ A означает 10, а C — 12. Чётность проверяется по значениям разрядов, значащая длина — после исключения начальных нулей.
• Отбросить ноль либо разрешить 07. В правильном выражении ↗ отдельное число 0 допустимо, но его нельзя продолжать цифрой. Запрет ведущего нуля относится к записи числа; он не запрещает нулевое или отрицательное значение всего выражения.