Тип 3
За плечами у нас разобранные алгоритмы решения первых двух типов 24 заданий ЕГЭ. Теперь же переходим к третьему. Здесь нам будут встречаться формулировки «символы не стоят рядом».
Сразу же здесь хочется как-то разделить такие символы, чтобы они действительно не стояли рядом в итоговых подстроках. В этом и будет заключаться суть одного из самых эффективных и популярных методов для решения 24 заданий третьего типа — метода замены и разделения.
В данной статье мы как раз и рассмотрим применение данного метода на нескольких примерах и сравним его с решением с помощью регулярных выражений.
Алгоритм решения
Начнём с абстрактной задачи. Представим, что у нас есть строка «ABCAABACACAB». В неё нужно найти подстроку максимальной длины, в которой символы A и B не стоят рядом (именно в таком порядке).
Для начала стоит найти все пары «AB» в строке. Отметим их на рисунке оранжевым цветом.
Теперь разделим всю строку на 4 части по этим парам. То есть буквально проведём «границу» внутри пары «AB». Получим такие подстроки: «A», «BCAA», «BACACA», «B».
Иными словами, можно сказать, что мы заменили пары «AB» на такую подстроку с пробелом между этими буквами: «A B». И затем разделили всю строку по пробельному символу. В этом и заключается метод замены и разделения:
- Заменить искомую пару на подстроку, в которой есть символ-разделитель;
- Разделить всю строку на подстроки по этому символу-разделителю
В Python это можно записать так:
И дальше можно легко найти подстроку с максимальной длиной, например так:
Правда, зачастую требуется, чтобы буквы не стояли рядом друг с другом вне зависимости от порядка следования. В таком случае придётся заменять не только пары «AB», но и «BA».
Покажем это на примере задания с такой формулировкой:
«Текстовый файл состоит не более, чем из 107 строчных букв английского алфавита. Найдите максимальную длину подстроки, в которой символы a и d не стоят рядом.»
Здесь нам нужно будет пары «ad» на «a d» и «da» на «d a». И далее разделить всю строку по пробельному символу. В коде это будет выглядеть так:
Запускаем его и получаем ответ — число 2252.
Продемонстрируем некоторые другие решения. Так, наши замены можно записать в одну строку:
Можно в цикле перебирать все подстроки между «ad» и «da» и с помощью переменной-счётчика подсчитывать количество символов внутри таких подстрок. А максимальную длину фиксировать в отдельной переменной:
И перейдём к регулярным выражениям. Давайте составим строку, которая будет служить нам примером, и визуализируем её. Пусть это будет строка «adссacacacadcacad». Выделим на рисунке искомые пары символов.
То есть нам нужно, чтобы и до, и после нашей строки находилась пара символов «ad» (или «da»). Причём между этими парами можем захватывать 1 и более (квантификатор «+») любых символов.
Но нам также нужно учесть, что этот квантификатор должен быть «ленивым», то есть захватывать как можно меньше символов между парами «ad» (или «da»).
Иначе здесь вместо двух подстрок «ссacacac» и «cac» получим всего одну – «ссacacacadcac», которая находится между самой первой и самой последней парой «ad».
Главное – не забыть добавить еще два символа, ведь мы ищем подстроки строго между парами «ad», но не учитываем, что в эту подстроку входят оба символа: «d» слева и «a» справа.
И это самая большая проблема. Ведь можно попросту забыть про эти «+2» символа. А составить регулярное выражение, которое будет автоматически учитывать границы подстрок и включать в них по одному символы из пары «ad»/«da», будет довольно сложно.
С общей логикой разобрались, переходим к составлению регулярного выражения. Для наглядности будем составлять его из трёх частей, но вы можете писать все части в одном регулярном выражении.
Начнем с того, что определим выражение для ленивого поиска любого символа в количестве 1 и более штук:
Теперь переходим к определению пар «ad» или «da». Нам на помощь придут ретроспективная и опережающая проверки.
Для определения пары «слева» от нужной подстроки напишем такое выражение с ретроспективной проверкой «(?<=…)»:
По аналогии будем определять пару и «справа», только теперь используя опережающую проверку «(?=…)»:
Соединяем три части в одно выражение через f-строки:
Теперь допишем чтение данных из файла, наши шаблоны регулярных выражений и поиск подстроки с наибольшей длиной:
В результате получим все тот же ответ — 2252. Но такое решение будет куда сложнее написать, а главное — осознать, чем то, которое мы привели в начале через замену и разделение.
Какой метод выбрать — решать вам. Но далее мы сконцентрируемся именно на методе замены и разделения.
Пример 1
Следующим рассмотрим такое задание:
«Текстовый файл состоит из арабских цифр (0, 1, …, 9).
Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет символов 0, стоящих рядом.»
В решении этого задания вообще не должно возникнуть сложностей. Достаточно просто разделить пары нулей пробелом и разбить по пробельному символу всю строку:
Запускаем программу и получаем ответ — 977.
Пример 2
Рассмотрим похожее задание:
«Текстовый файл состоит из арабских цифр (0, 1, …, 9).
Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет символов 1 и 2, а также 1 и 3 стоящих рядом.»
Здесь нам предстоит заменить такие пары:
- «12» на «1 2»
- «21» на «2 1»
- «13» на «1 3»
- «31» на «3 1»
Проводим четыре замены и разделяем строку по пробельному символу:
После запуска нашей программы получим число 339, которое и запишем в ответ.
Пример 4
В конце у нас будет такое задание:
«Текстовый файл состоит не более, чем из 1 200 000 прописных символов латинского алфавита.
Определите максимальное количество идущих подряд символов, среди которых любые два символа из набора Q, R, S в различных комбинациях (с учётом повторений) не стоят рядом.»
Тут уже интереснее. Комбинаций пар из символов QRS целых 6. Чтобы не писать 6 строк замен, можно поступить хитрее — заменить каждую букву на один любой символ, например точку:
Теперь расставляем пробелы между точками:
И дальше всё как обычно — разделяем по пробелу и ищем самую длинную подстроку:
В результате работы программы получим число 544, которое и будет ответом на данное задание.
Как вы могли понять, не все 24 задания следует решать с помощью регулярных выражений. Зачастую более простые способы не только отлично справляются с решением, но и являются куда более интуитивно понятными.
В следующей статье мы еще раз убедимся в этом при разборе заключительного — четвёртого — типа 24 заданий.