Python: пошаговая работа окна в задании №24

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

Учебные данные и переменные

Для пошагового выполнения используется учебная строка ABCBCCBCF, а требуемое количество вхождений уменьшено со 190 до 2. Это отдельный пример, а не содержимое или заявленный фрагмент файла 88B226.txt. В нём девять символов с индексами от нуля до восьми.

индекс: 012345678
строка: ABCBCCBCF

Окно — непрерывный фрагмент между двумя включёнными границами. Переменная l хранит индекс его первого символа, r — последнего. Строка при сдвиге границ не изменяется: программа только начинает рассматривать другой её участок.

count хранит количество целых вхождений BC внутри окна. Оставшаяся без своей B буква C парой не считается. best хранит наибольшую длину среди уже рассмотренных окон, где пар ровно две. Поэтому текущее окно может стать короче, а best останется прежним.

Вспомогательная переменная pair содержит две проверяемые буквы. Переменная size получает длину текущего подходящего окна. При включённых границах эта длина равна r-l+1: если обе границы указывают на один символ, длина равна единице.

Та же программа на короткой строке

Чтение файла заменено присваиванием учебной строки, обе проверки числа 190 заменены проверками числа 2. Остальные команды и их порядок совпадают с программой основного разбора.

s = "ABCBCCBCF"

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 > 2:
        pair = s[l:l+2]
        if pair == "BC":
            count -= 1
        l += 1
    if count == 2:
        size = r-l+1
        best = max(
            best, size
        )
print(best)

range(len(s)) даёт индексы от нуля до восьми. На каждом шаге сначала добавляется новый правый символ и учитывается возможная новая пара. Затем while убирает лишние вхождения слева. Только после этого проверяется точное равенство и обновляется ответ. Отступы показывают, какие команды относятся к каждому циклу и условию.

Команда count += 1 означает прибавление единицы к прежнему счётчику, а не присваивание ему единицы. Аналогично count -= 1 уменьшает прежнее значение. После завершения очередного шага эти переменные не обнуляются: следующий шаг продолжает работу с уже найденным началом и количеством пар. Начальные присваивания стоят перед циклом именно поэтому.

От первого символа до двух пар

Индекс 0: добавлена A

Текущее окно A, длина 1, границы l=0, r=0. Проверка r > 0 ложна: предыдущей буквы ещё нет. Пара не создаётся, count = 0. Цикл сжатия не запускается, условие count == 2 не выполнено, best = 0.

Индекс 1: добавлена B

Окно AB, длина 2. Теперь r > 0, поэтому pair = s[0:2] даёт AB. Это не BC: счётчик остаётся нулевым. Сжатия и обновления ответа нет; l = 0, best = 0.

Индекс 2: добавлена C

Окно ABC, длина 3. Срез s[1:3] равен BC, поэтому команда count += 1 меняет счётчик с нуля на единицу. Это первое целое вхождение. Лишних пар нет, но требуемые две ещё не набраны: best = 0.

Индекс 3: добавлена B

Окно ABCB, длина 4. Последняя пара CB не совпадает с BC, поэтому count = 1. Новая B сама по себе не образует нужного вхождения. Начало остаётся нулевым, ответ пока не обновляется.

Индекс 4: добавлена C

Окно ABCBC, длина 5. Последняя пара BC увеличивает count до двух. Условие count > 2 ложно, значит начало сдвигать не требуется. Равенство выполнено: size = 4-0+1 даёт пять, а max(0, 5) устанавливает best = 5.

Удлинение без новых вхождений

Индекс 5: добавлена C

Окно ABCBCC, длина 6. Новая пара CC не меняет count = 2. Сжатия нет; size = 5-0+1 даёт шесть. Поскольку max(5, 6) равен шести, best = 6. Подходящий фрагмент может включать буквы, не принадлежащие ни одному BC.

Индекс 6: добавлена B

Окно ABCBCCB, длина 7. Проверяется CB, поэтому число целых пар остаётся равным двум. Длина 6-0+1 больше прежней: best = 7. Конечная B входит в длину, но без следующей C нового вхождения ещё нет.

Индекс 7: третья пара и два удаления

После добавления C окно временно равно ABCBCCBC, длина 8. Последняя пара s[6:8] — это BC, поэтому count увеличивается с двух до трёх. Такое окно не подходит. Его длина восемь не сравнивается с ответом: сначала выполняется while count > 2.

Первое выполнение while: исключается A

До удаления: ABCBCCBC, длина 8, l = 0, count = 3. Срез s[l:l+2] равен AB. На удаляемой A вхождение BC не начинается, поэтому счётчик не уменьшается.

Команда l += 1 переносит начало на индекс один. После удаления: BCBCCBC, длина 7, l = 1, count = 3. Три пары сохранились целиком. Цикл снова проверяет своё условие: оно по-прежнему истинно, значит одного удаления недостаточно.

Второе выполнение while: исключается B

До удаления: BCBCCBC, длина 7, l = 1. Теперь s[1:3] равно BC. Исключение начальной B разрушит первое вхождение, поэтому count -= 1 меняет три на два. Затем l += 1 устанавливает начало на индекс два.

После удаления: CBCCBC, длина 6, l = 2, count = 2. Буква C бывшей первой пары осталась, но её B уже снаружи. Новая проверка count > 2 ложна: цикл завершён. Равенство выполнено, size = 7-2+1 даёт шесть. Команда max(7, 6) сохраняет best = 7.

Проверка пары стоит до увеличения l, потому что относится к символу, который сейчас исключается. Цикл while нужен именно для повторения: одна команда if убрала бы только A и оставила лишнюю пару.

Индекс 8 и итог

Добавляется F. Окно CBCCBCF, длина 7, границы l=2, r=8. Последняя пара CF не увеличивает count = 2. Сжатия нет. Вычисляется size = 8-2+1, затем max(7, 7); best остаётся равным семи. Цикл заканчивается, программа печатает 7.

Максимальная длина достигнута дважды: для ABCBCCB и CBCCBCF. Программа сохраняет только длину, поэтому отдельного выбора между этими строками не делает. Самое длинное промежуточное окно длины восемь не подходит: в нём три пары.

Проверка состояния после шага

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

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

Значение best, в отличие от текущей длины, никогда не уменьшается. Оно связывает разные шаги: после сжатия окна предыдущий результат не теряется. Именно поэтому программа выводит максимум за весь проход, а не длину последнего подходящего окна.

Возврат к полному файлу

В исходной программе строка читается из 88B226.txt, полученного из вложения задания. В проверках while count > 190 и if count == 190 снова используется число 190. На полном файле результат равен 2287 символам; учебный результат семь относится только к строке выше. При отсутствии подходящего окна начальное значение best = 0 так и осталось бы нулём.

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