Навигация по странице
Тип 4
Последний, четвёртый, тип 24 заданий можно отличить по фразе «символ/подстрока встречается не более N раз».
Сразу отметим, что если в условии речь идёт про один символ, то такое задание можно решить регулярными выражениями. Само выражение будет выглядеть немного громоздко, но до него можно дойти логически.
Однако если дана подстрока, которая должна встречаться определённое количество раз, то просто «в лоб» решить такое задание регулярными выражениями не получится. Придётся либо прибегать к заменам, либо выстраивать довольно сложные выражения. В таком случае можно применять метод двух указателей.
В основе метода двух указателей заложена довольно простая идея: мы используем две переменные, которые перемещаются по массиву значений в зависимости от условий задачи.
Разберём этот метод на таком примере: «Нужно найти максимальное количество идущих подряд символов, среди которых символ Z встречается ровно 2 раза». Искать будем в следующей строке: «VZOVZOZOVVOVOVZZ».
На исходной позиции оба указателя находятся в начале строки, то есть имеют индекс 0.
Далее мы передвигаем правый указатель (здесь он выделен зелёным цветом) по строке. На каждом шаге проверяем, является ли текущий символ строки символом Z. Если доходим до Z, то увеличиваем счетчик cnt_z на 1. Пока количество символов Z равно 2, мы обновляем значение максимальной длины строки max_len (максимально длинная подстрока выделена зелёным).
Это все повторяется до тех пор, пока количество Z, как и значение счетчика cnt_z, не будет превышать значение 2. В таком случае начинает движение левый указатель.
При этом если на позиции левого указателя находится Z, уменьшаем счетчик cnt_z. Это позволяет нам «сужать» окно, чтобы количество символов Z не превышало 2.
Когда левый указатель доходит до символа Z, значение счетчика снова становится равным двум. Следовательно, мы снова вычисляем длину строки и проверяем, больше ли она максимальной. Если больше, то обновляем максимум, если нет – просто продолжаем выполнение кода дальше.
В нашем примере правому указателю достаточно будет дойти до символа, стоящего перед следующей буквой Z. Тогда же значение счётчика будет равным двум, а длина подстроки между левым и правым указателем будет максимальной (12 символов).
Код хоть и продолжит исполняться, но значения максимальной длины подстроки больше 12 уже не получим.
Давайте реализуем этот алгоритм на языке Python.
Инициализируем все переменные:
- data – строка, в которой будет происходить поиск
- n – количество символов в этой строке (длина строки)
- lt – левый указатель
- cnt_z – счётчик символов Z
- max_len – максимальная длина подстроки
data = "VZOVZOZOVVOVOVZZ"
n = len(data)
lt = 0
cnt_z = 0
max_len = 0
В цикле for перемещаем правый указатель по строке data. Если текущий символ, на который указывает правый указатель, равен Z, то увеличиваем значение cnt_z.
for rt in range(n):
if data[rt] == 'Z':
cnt_z += 1
Внутри этого же цикла запускаем цикл while пока значение cnt_z больше 2. Здесь проверяем, что уже левый указатель указывает на Z, в таком случае уменьшаем значение cnt_z. В противном случае просто увеличиваем значение lt – сдвигаем левый указатель дальше по строке.
while cnt_z > 2:
if data[lt] == 'Z':
cnt_z -= 1
lt += 1
В конце цикла for проверяем, если количество Z равно 2, то вычисляем длину подстроки между левым и правым указателем и обновляем max_len при необходимости.
if cnt_z == 2:
max_len = max(max_len, rt - lt + 1)
Весь код будет выглядеть так:
data = "VZOVZOZOVVOVOVZZ"
n = len(data)
lt = 0
cnt_z = 0
max_len = 0
for rt in range(n):
if data[rt] == 'Z':
cnt_z += 1
while cnt_z > 2:
if data[lt] == 'Z':
cnt_z -= 1
lt += 1
if cnt_z == 2:
max_len = max(max_len, rt - lt + 1)
print(max_len)
>>>12
Теперь вы умеете пользоваться методом двух указателей для поиска максимальной длины подстроки, в которой символ или подстрока встречается заданное количество раз.
Но, как мы ранее условились, сначала разберём решение 24 задания 4 типа через регулярные выражения, а затем уже вернёмся к методу двух указателей.
Рассмотрим такую формулировку:
Задание 2408
«Текстовый файл состоит не более чем из 106 символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых символ Z встречается не более одного раза.
Для выполнения этого задания следует написать программу»
Здесь задача максимально похожа на уже разобранный пример. Разве что количество Z теперь не равно 2, а не более 1.
Давайте сначала составим регулярное выражение, на простом примере. Использовать в качестве этого примера будем ту же самую строку, что и в прошлый раз. И также сначала найдём подстроку с двумя Z, а потом перепишем код для поиска подстроки, в которой Z встречается не более одного раза.
Разложим нужную нам подстроку на несколько частей. Мы здесь видим, что сначала в строку входит любое количество символов «не Z» (O и V).
Далее можно составить такую группу, в которой будет один символ Z и любое количество остальных символов. Тут будет 2 такие группы. Первая состоит всего из двух символов – «ZO».
А вторая включает в себя все остальные – «ZOVVOVOV»
И тогда искомая подстрока у нас будет складываться из двух групп: зелёной и оранжевой.
Реализуем этот алгоритм на Python.
Начнём с первой «зелёной» группы. Она включает в себя все символы кроме Z с квантификатором «*» (0 и более повторений).
not_z = r'([^Z]*)'
Далее идёт «оранжевая группа»: она у нас будет группой без захвата содержимого и включает в себя один символ Z и все символы кроме Z с квантификатором «*». И такая группа должна повторяться ровно 2 раза:
two_z_group = r'(?:Z[^Z]*){2}'
И самое интересное. Дело в том, что нам необходимо искать пересекающиеся последовательности. Ведь из-за того, что по умолчанию регулярные выражения ищут непересекающиеся последовательности, то сначала наш код нашёл бы такую подстроку:
И продолжилось выполнение программы сразу после последней оранжевой буквы O. Значит, правильная последовательность даже не была бы рассмотрена.
В Python есть несколько способов заставить регулярные выражения работать с пересекающимися совпадениями. Один из таких – использовать уже знакомую нам опережающую проверку «(?=…)». Она лишь проверяет, что после предыдущего символа есть какая-то последовательность, но не «потребляет» символы из строки.
В нашей задаче мы можем поместить внутри опережающей проверки нашу «оранжевую» группу two_z_group:
la_z_group = rf'(?=({two_z_group}))'
Обратите внимание, что мы дополнительно помещаем two_z_group в круглые скобки, то есть создаём группу с захватом содержимого, значения из которой будем использовать в дальнейшем.
Теперь осталось соединить обе группы – not_z и la_z_group в единое регулярное выражение:
pattern = rf'{not_z}{la_z_group}'
Можем смело вызывать функцию, в которую и передадим это выражение. Но здесь нам нужно будет работать с группами, так что проще вызвать функцию findall() вместо finditer().
Сравнить количество кода для каждой функции вы можете на примере ниже:
matches = re.findall(pattern, data)
res = max([len(match[0] + match[1])
for match in matches])
# === === === === === === === === === #
matches = re.finditer(pattern, data)
res = max([len(match.group(1) + match.group(2))
for match in matches])
Дописываем программу для решения нашего примера:
import re
data = "VZOVZOZOVVOVOVZZ"
not_z = r'([^Z]*)'
two_z_group = r'(?:Z[^Z]*){2}'
la_z_group = rf'(?=({two_z_group}))'
pattern = rf'{not_z}{la_z_group}'
matches = re.findall(pattern, data)
res = max([len(match[0] + match[1])
for match in matches])
print(res)
В результате получаем всё ту же длину строки – 12.
Мы вывели общий шаблон для решения заданий такого типа. Теперь лишь осталось немного поправить код, с учётом условия разбираемого задания. В нём сказано, что символ Z должен встречаться не более одного раза: то есть 0 или 1 раз, что соответствует квантификатору «?».
Значит, в представленном выше коде меняем «{2}» на «?», а также имена переменных на более подходящие по смыслу.
В итоге получаем такой код:
import re
with open('2408.txt', 'r') as file:
data = file.readline()
not_z = r'([^Z]*)'
z_and_any = r'(?:Z[^Z]*)?'
la_z_group = rf'(?=({z_and_any}))'
pattern = rf'{not_z}{la_z_group}'
matches = re.findall(pattern, data)
res = max([len(match[0] + match[1])
for match in matches])
print(res)
Запускаем его и получаем ответ на это задание – число 43.
Пример 1
Теперь перейдём к заданию, в котором требуется, чтобы целая подстрока, а не один символ, встречалась определённое количество раз.
Формулировка будет такой:
Задание 2407
«Текстовый файл состоит из символов F, G, Q, R, S и W. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока FSRQ встречается ровно 80 раз.
Для выполнения этого задания следует написать программу»
Как мы уже говорили ранее, в таком здании не обойтись без метода двух указателей. Давайте приступим к его реализации.
Для начала откроем файл, считаем данные в строку data и инициализируем левый указатель, счётчик вхождений подстроки «FSRQ» и переменную, которая будет хранить максимальную длину подстроки.
with open('2407.txt', 'r') as file:
data = file.readline()
n = len(data)
lt = 0 # Левый указатель
cnt = 0 # Количество вхождений 'FSRQ'
max_len = 0 # Максимальная длина подстроки
Далее в цикле for будем проверять, есть ли на текущей позиции правого указателя подстрока «FSRQ», если такая имеется, то увеличиваем счётчик cnt.
# Проходим по строке с правым указателем
for rt in range(n - 3):
# Проверяем, есть ли 'FSRQ' на текущей позиции
if data[rt:rt+4] == 'FSRQ':
cnt += 1
Далее идёт проверка количества вхождений «FSRQ» в цикле while. Если таких подстрок больше 80, то сдвигаем левый указатель. А также если текущей позицией левого указателя является подстрока «FSRQ», то уменьшаем значение cnt.
# Если количество вхождений 'FSRQ' превышает 80,
# сдвигаем левый указатель
while cnt > 80:
if data[lt:lt+4] == 'FSRQ':
cnt -= 1
lt += 1
Теперь осталось написать вычисление максимальной длины, когда подстрок «FSRQ» ровно 80 штук. И вывести на экран значение max_len.
# Если количество вхождений 'FSRQ' равно 80,
# обновляем максимальную длину
if cnt == 80:
max_len = max(max_len, rt - lt + 4)
print(max_len)
Вся программа для решения данного задания выглядит следующим образом:
with open('2407.txt', 'r') as file:
data = file.readline()
n = len(data)
lt = 0 # Левый указатель
cnt = 0 # Количество вхождений 'FSRQ'
max_len = 0 # Максимальная длина подстроки
# Проходим по строке с правым указателем
for rt in range(n - 3):
# Проверяем, есть ли 'FSRQ' на текущей позиции
if data[rt:rt+4] == 'FSRQ':
cnt += 1
# Если количество вхождений 'FSRQ' превышает 80,
# сдвигаем левый указатель
while cnt > 80:
if data[lt:lt+4] == 'FSRQ':
cnt -= 1
lt += 1
# Если количество вхождений 'FSRQ' равно 80,
# обновляем максимальную длину
if cnt == 80:
max_len = max(max_len, rt - lt + 4)
print(max_len)
Осталось запустить её, немного подождать и получить ответ – 2379.
Пример 2
Давайте еще разберем решение заданий четвёртого типа методом замены и разделения строки. Решение данным методом занимает куда меньше кода, чем методом двух указателей. К тому же порой для использования регулярных выражений все равно придётся делать замену.
Задание 2403
«Текстовый файл состоит из символов A, B, C, D, E и F.
Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых пара символов CD (в указанном порядке) встречается ровно 160 раз.
Для выполнения этого задания следует написать программу»
Сначала пробежимся по решению с использованием регулярных выражений, а уже затем решим это задание через замены.
Считаем данные из файла и сразу заменим пару «CD» на другие символы, например, на пару дефисов «–».
import re
with open('2403.txt', 'r') as file:
data = file.readline()
data = re.sub('CD', '--', data)
not_CD = r'(-?[^-]*)'
Зачем это нужно? Дело в том, что запись, которую мы использовали раньше для одной буквы, в случае с парой CD будет срабатывать неверно. То есть вместо того, чтобы искать любые символы, кроме пары CD, она будет искать любые символы, кроме С и кроме D, что нас, откровенно говоря, не устраивает.
Для примера, в строке «CCAAABCDAABCCD» под регулярное выражение ([^CD]*) будет найдено всего две подстроки: «AAAB» и «AAB».
Хотя нам нужны были подстроки «CCAAAB» и «AABC».
Значит, нам следует заменить каждую пару CD на другие символы (у нас это «–») и переписать выражение так, чтобы сначала было либо 0, либо 1 вхождение символа C или D, а затем шёл любой символ, кроме этих двух, в количестве 0 или более (квантификатор «*»).
В таком случае изменяем и вторую группу, в которой ищем последовательность из пар CD в количестве 160 штук, разделённых любыми символами кроме C или D.
CD_and_any = r'(?:--[^-]*){160}-?'
То есть у нас сначала идёт группа из пары CD, за которой следуют любые символы кроме C или D, таких групп ищем 160, а в конце требуем, чтобы было от 0 до 1 вхождения символа C или D.
Далее описываем в выражении опережающую проверку:
la_CD_group = rf'(?=({CD_and_any}))'
И соединяем все группы в одно регулярное выражение:
pattern = rf'{not_CD}{la_CD_group}'
Весь код будет выглядеть так:
import re
with open('2403.txt', 'r') as file:
data = file.readline()
data = re.sub('CD', '--', data)
not_CD = r'(-?[^-]*)'
CD_and_any = r'(?:--[^-]*){160}-?'
la_CD_group = rf'(?=({CD_and_any}))'
pattern = rf'{not_CD}{la_CD_group}'
matches = re.findall(pattern, data)
res = max([len(match[0] + match[1])
for match in matches])
print(res)
После его запуска и некоторого периода ожидания получаем ответ – 9712.
Но теперь рассмотрим, как можно решить это задания без регулярных выражений.
Также считываем данные из файла:
with open('2403.txt', 'r') as file:
data = file.readline()
Но теперь замена будет другая: пару «CD» заменяем на «C D» и разделяем строку по пробельному символу.
data = data.replace("CD", "C D").split()
Создаём переменную, в которой будем хранить максимальную длину последовательности:
max_len = 0
Далее пишем цикл for, который проходит по индексам списка data. Диапазон range(len(data) – 160) гарантирует, что мы не выйдем за пределы этого списка при создании подстроки длиной в 161 элемент.
for i in range(len(data) - 160):
substring = "".join(data[i:i + 161])
max_len = max(max_len, len(substring))
На каждой итерации этого цикла происходит следующее:
- data[i:i + 161] создает список из 161 элемента начиная с индекса i.
- “”.join(data[i:i + 161]) объединяет элементы списка в одну строку substring.
- len(substring) вычисляет длину этой строки.
- max(max_len, len(substring)) обновляет значение max_len, если текущая подстрока длиннее предыдущего максимального значения.
Это можно представить так: рассмотрим часть исходной строки «…CDAAABCDAABCCD…». В ней расставим пробелы между символами пары CD и разделим строку на список подстрок, которые начинаются с D и заканчиваются C.
Далее собираем 160 таких кусочков исходной строки вместе и получаем подстроку, в которой пара CD встречается ровно 160 раз.
Осталось только вычислить длину каждой такой подстроки и найти наибольшее значение из всех длин.
А полный код для решения этого задания через замены и разделение строки будет выглядеть так:
with open('2403.txt', 'r') as file:
data = file.readline()
data = data.replace("CD", "C D").split()
length = 0
for i in range(len(data) - 160):
substring = "".join(data[i:i + 161])
length = max(length, len(substring))
print(length)
В результате получаем всё то же значение 9712, которое и даём в ответ.