Что проверяет задание

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

Определения

Строка, последовательность символов. Индексация обычно с нуля или с единицы, на ответ про длину это не влияет.

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

Алфавит допустимых символов, множество, из которого должна состоять искомая подстрока.

Разделитель, символ, который разрезает строку на куски. Максимум среди длин кусков, наибольшая подстрока без этого разделителя.

Окно, текущий рассматриваемый отрезок [L, R]. При движении правого конца окно расширяют, при нарушении свойства левый конец сдвигают вправо.

Корректное выражение, строка, построенная по грамматике: например, число из цифр, сумма чисел со знаком + между ними, скобочная последовательность. «Корректность» задаётся правилами, а не смыслом вычисления.

Серия, максимальный кусок одинаковых символов подряд. Ограничение «не больше двух одинаковых подряд», ограничение на длину серии.

Количество различных символов в окне, сколько уникальных значений попало в текущую подстроку. Это не длина окна.

Что именно оптимизируют

«Наибольшая подстрока, состоящая только из …», максимум длины среди подстрок, целиком лежащих в допустимом алфавите.

«Наименьшая подстрока, содержащая …», минимум длины среди подстрок, которые уже набрали нужное свойство.

Путать максимум и минимум, а также «состоит только» и «содержит хотя бы» нельзя: это противоположные фильтры.

Общий алгоритм решения

1. Переформулировать свойство подстроки так, чтобы его можно было проверять локально или через счётчики в окне.
2. Если свойство, «не содержит данный символ», разрезать строку по этому символу и взять экстремум длин кусков.
3. Если свойство накапливается (число определённых символов, число серий), вести окно: правый указатель идёт вперёд, левый догоняет, когда свойство нарушено или, наоборот, когда свойство уже выполнено и ищут минимум.
4. Для грамматик выражений определить, какие символы начинают и заканчивают корректный кусок, и какие переходы допустимы.
5. Обновлять ответ на каждом шаге, когда окно допустимо.
6. Следить за пустым ответом: если подходящих подстрок нет, условие обычно всё же гарантирует существование, но нулевая длина возможна только если её явно допускают.

Программа построчно

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

Разберём программу на условии:

Текстовый файл состоит из символов латинского алфавита и цифр. Определите максимальную длину подстроки, которая состоит из повторяющегося слова «mk». Последнее слово в цепочке может быть неполным.

from re import findall

s = open("24.txt").read().strip()
pattern = r"(?:mk)+(?:m)?"
klop = findall(pattern, s)
print(len(max(klop, key=len)))

from re import findall - подключаем функцию поиска по шаблону из модуля re (regular expressions, регулярные выражения).

s = open("24.txt").read().strip() - вся строка файла. Подробно - в разделе «Чтение строки из файла».

pattern = r"(?:mk)+(?:m)?" - шаблон: «mk» один или несколько раз подряд, а в конце, возможно, ещё «m» (неполное слово). Подробно - в разделе «Регулярные выражения».

klop = findall(pattern, s) - список всех кусков строки, подходящих под шаблон.

print(len(max(klop, key=len))) - самый длинный кусок и его длина. Подробно - в разделе «findall и самая длинная подстрока».

Чтение строки из файла

s = open("24.txt").read().strip()

• open("24.txt") - открываем файл, который лежит рядом с программой;
• .read() - читаем всё содержимое одной строкой;
• .strip() - убираем пробелы и перевод строки по краям. Без этого последний символ строки - '\n', и он может испортить подсчёт (например, в задаче «нет двух одинаковых символов рядом» перевод строки удлинит цепочку на 1).

К символам строки обращаются по номеру: s[0] - первый, s[i] - i-й, s[i:i + 3] - кусок из трёх символов, начиная с i.

Регулярные выражения

Регулярное выражение - шаблон, описывающий, какие строки подходят. Запись r"…" - «сырая» строка: обратная косая черта \ в ней остаётся как есть.

• mk - ровно эти символы подряд;
• [FPW] - один любой символ из перечисленных; [^Q] - любой символ, кроме Q;
• [4a] - «a» или «4» (по правилам leet буква может быть заменена цифрой);
• \d - любая цифра;
• + после элемента - «один или больше раз подряд»: [FPW]+ - цепочка только из F, P, W;
• ? после элемента - «ноль или один раз», то есть необязательно;
• (?:…) - скобки-группа: к ней применяют + или ? целиком. (?:mk)+ - «mk», «mkmk», «mkmkmk»…;
• | - «или»: (?:prlnx|prln|prl|pr|p) - один из вариантов.

Шаблон «повторяющееся слово, последнее может быть неполным» для слова prlnxm:

pattern = r"(?:prlnxm)+(?:prlnx|prln|prl|pr|p)?"

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

findall и самая длинная подстрока

klop = findall(pattern, s)
print(len(max(klop, key=len)))

• findall(шаблон, строка) - список всех непересекающихся кусков, подходящих под шаблон, слева направо. Каждый кусок захватывается максимально длинным;
• max(klop, key=len) - самый длинный кусок: key=len говорит «сравнивай по длине», иначе строки сравнивались бы по алфавиту;
• len(…) - его длина, это и есть ответ.

Разрезание строки: replace и split

«Максимальная длина подстроки, в которой нет пары AK». Разрежем строку между A и K в каждой такой паре - получатся куски без пары:

s = s.replace("AK", "A K")
print(max(len(part) for part in s.split()))

• s.replace("AK", "A K") - каждую пару AK заменяем на «A K»: вставили пробел между буквами. Буквы при этом остаются в своих кусках: A - в конце левого, K - в начале правого;
• s.split() - режем по пробелам;
• max(len(part) for part in …) - длина самого длинного куска.

Метод окна

«Максимальная длина подстроки, где символ K встречается не более 1 раза». «Окно» - подстрока от left до right. Правая граница идёт по строке, а левая сдвигается, когда окно перестаёт подходить.

k = 1
left = 0
count = 0
best = 0
for right in range(len(s)):
    if s[right] == "K":
        count += 1
    while count > k:
        if s[left] == "K":
            count -= 1
        left += 1
    best = max(best, right - left + 1)
print(best)

• count - сколько символов K сейчас в окне;
• символ s[right] вошёл в окно - если это K, увеличиваем счётчик;
• пока K больше допустимого - убираем символы слева: если уходит K, уменьшаем счётчик;
• right - left + 1 - длина окна; запоминаем наибольшую.

Каждый символ входит в окно и выходит из него один раз, поэтому программа работает быстро даже на строке из миллиона символов.

Длина цепочки: cur и best

Когда свойство проверяется для соседних символов («нет двух одинаковых рядом», «цифры убывают»), идём по строке и считаем длину текущей цепочки:

best = 1
cur = 1
for i in range(1, len(s)):
    if s[i] != s[i - 1]:
        cur += 1
    else:
        cur = 1
    best = max(best, cur)
print(best)

• cur - длина цепочки, которая заканчивается на символе s[i];
• условие выполнено для пары s[i - 1], s[i] - цепочка продолжается: cur += 1;
• не выполнено - новая цепочка начинается с s[i]: cur = 1;
• best - самая длинная цепочка за всё время.

Цифры в строке - символы, но сравниваются так же, как числа: "7" < "9" верно.

Подсчёт фрагментов

«Сколько раз встречается BAB, перекрывающиеся вхождения считаются все»:

count = 0
for i in range(len(s) - 2):
    if s[i:i + 3] == "BAB":
        count += 1
print(count)

• s[i:i + 3] - кусок из трёх символов, начиная с позиции i;
• проверяем каждую позицию, поэтому в «BABAB» найдутся оба вхождения (с позиций 0 и 2);
• range(len(s) - 2) - последний фрагмент начинается за 2 символа до конца строки.

Встроенный s.count("BAB") перекрывающиеся вхождения не считает: для «BABAB» он даст 1.

Частота символов: словарь

«Какой символ чаще всего встречается сразу после H»:

count = {}
for i in range(len(s) - 1):
    if s[i] == "H":
        nxt = s[i + 1]
        count[nxt] = count.get(nxt, 0) + 1
print(max(count, key=count.get))

• count - словарь «символ → сколько раз он стоял после H»;
• count.get(nxt, 0) - текущее значение, а если символа в словаре ещё нет - 0;
• max(count, key=count.get) - ключ (символ), у которого значение наибольшее.

Калькулятор: корректное выражение

В файле - цифры и знаки операций (-, *, +). Нужна максимальная длина непрерывного фрагмента, который является корректным арифметическим выражением: числа без ведущих нулей, два знака операций подряд нельзя, число 0 пишется одной цифрой.

Шаблон числа собирают в переменную и подставляют в f-строку:

from re import findall

s = open("24.txt").read().strip()
num = r"(?:[6789][06789]*|0)"
pat = rf"{num}(?:[-*]{num})+"
res = findall(pat, s)
print(len(max(res, key=len)))

• num - одно число: либо 0, либо первая цифра из разрешённых ненулевых, дальше - любые из набора цифр условия;
• pat - число, затем один или больше раз «оператор + число» (знак + у группы в regex - «один или больше»);
• findall находит все такие куски, max(..., key=len) - самый длинный, len - ответ.

Если в условии другие цифры или операции - правят классы в num и в [-*].

Буква перед выражением. «Подстрока из буквы A, за которой следует корректное выражение» - в начало шаблона добавляют букву: pat = rf"A{num}(?:[-*]{num})+". Длина считается вместе с буквой.

Значение выражения равно нулю. Сначала находят все корректные выражения, затем оставляют те, у которых значение 0 (порядок действий - как в математике: сначала *, потом +):

res = [p for p in findall(pat, s) if eval(p) == 0]
print(len(max(res, key=len)))

eval здесь безопасен: в куске только цифры и знаки из условия, не произвольный код.