Обработка символьной информации

В задании 24 дают файл — одну длинную строку примерно из миллиона символов. Нужно найти в ней самый длинный (иногда самый короткий) кусок, идущий подряд, с заданным свойством. Вот задача, которую мы решим в этой теме:

«Текстовый файл 24-6.txt состоит из десятичных цифр и знаков «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными числами (без знака). В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули. В ответе укажите количество символов.»

Перебрать все куски строки не получится — их сотни миллиардов. Поэтому строку проходят один раз и по дороге помнят только то, что нужно для ответа. Разберём, что значат слова условия:

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

1. Строка и цепочка — ты сейчас здесь: чтение файла и самая длинная цепочка.
2. Условия на соседей — одинаковые подряд, соседи различны, запретные пары.
3. Образцы и блоки — DOGDOG…, цепочки пар, палиндромы.
4. Скользящее окно — не более K и ровно K букв во фрагменте.
5. Позиции и границы — K подряд идущих вхождений, особые начало и конец.
6. Числа и выражения — регулярные выражения; решим задачу темы: ответ 172.
7. Выражения с условиями и баланс — дополнительный урок для сложных вариаций.

Что значит «идущие подряд символы»?

Кусок строки без пропусков: символы берут один за другим, ничего не выкидывая из середины. В строке AAAXAAAA самая длинная цепочка букв A — четыре, а не семь: чтобы получить семь, пришлось бы выкинуть X. Такой кусок ещё называют подстрокой или фрагментом.

В Python к символу обращаются по номеру — индексу. Счёт идёт с нуля: s[0] — первый символ, s[-1] — последний, len(s) — длина. Кусок вырезают срезом s[a:b]: от a включительно до b не включительно.

s = 'CABAC'print(s[0], s[4], s[-1], len(s))print(s[1:4])

Срез s[1:4] взял символы с номерами 1, 2 и 3 — правая граница не входит:

Если кусок задан двумя включёнными концами left и right, его длина — right - left + 1: символы с номерами 3, 4, 5 и 6 — это четыре символа, хотя 6 − 3 = 3.

Как прочитать строку из файла?

Одной строкой: s = open('24.txt').readline().strip(). Без strip() в конце останется перевод строки — лишний символ. readline() читает первую строку файла вместе с невидимым символом перевода строки, strip() убирает его. В учебном файле 24.txt одна строка — XXAXXXXBXX:

s = open('24.txt').readline().strip()print(s, len(s)) line = open('24.txt').readline()print(len(line), len(line.strip()))

С переводом строки символов 11, без него — 10. Если ищем «символы, отличные от A», перевод строки тоже посчитается — и ответ станет на единицу больше. Поэтому strip() пишем всегда.

Как найти самую длинную цепочку букв X, не перебирая все куски строки?

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

s = open('24.txt').readline().strip() current = 0best = 0for c in s:    if c == 'X':        current += 1    else:        current = 0    best = max(best, current) print(best)

Пройди строку XXAXXXXBXX по шагам: заливка — текущая цепочка, скобка — лучшая из найденных.

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

В условии просят не длину самой длинной цепочки X, а номер её первого символа, а если таких цепочек несколько — последней из них. Что меняется?

Меняется только то, что запоминаем: вместе с длиной храним начало лучшей цепочки, а правило «при равенстве» записываем явно. Перед кодом ответь на три вопроса: какие куски подходят, что сравниваем, что выводим.

s = 'XXAXXBXXAX'current = 0best_length = 0best_start = 0for i in range(len(s)):    if s[i] == 'X':        current += 1    else:        current = 0    if current > 0 and current >= best_length:        best_length = current        best_start = i - current + 1 print(best_length, best_start)

Цепочка, которая кончается на символе i, начинается на i - current + 1. Проверка current > 0 не даёт «цепочке» нулевой длины на символе A занять место ответа. Три цепочки длины 2 начинаются с 0-го, 3-го и 6-го символа. Знак >= пускает более позднюю цепочку при равенстве, поэтому выбрана последняя. Для первой из равных нужен строгий >.

Нумерацию берут из условия: если символы считают с единицы, к индексу Python прибавляют 1.

• Подрядкусок без пропусков — подстрока
• Чтение файлаs = open('24.txt').readline().strip()
• Длина кускаright − left + 1 при включённых концах
• currentдлина цепочки, которая кончается на текущем символе
• bestобновлять после каждого символа
• При равенстве«>=» — последний из равных, «>» — первый