Обработка строк из файла

Что проверяет номер

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

Длинная строка (до миллиона символов). Надо найти самую длинную (или самую короткую) подстроку с заданным свойством: пара/тройка встречается ровно k раз, нет двух одинаковых подряд, корректное арифметическое или римское число и т. п.

Простыми словами

Представь очень длинную ленту с буквами. Глазами её не прочитать, поэтому мы ведём по ней пальцем и считаем.

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

Если условие сложнее, например «подстрока содержит нужный кусок ровно k раз», помогает окно. Запоминаем места, где встретился кусок, и держим только последние k. Как только добавилось новое место, самое старое выбрасываем. Между первым и последним местом как раз лежит нужная подстрока, и остаётся сравнить её длину с лучшей.

Двойной цикл с break

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

Идея: фиксируем начало i, наращиваем конец n, и как только условие сломано, цикл обрываем. Уже найденный максимум m не даёт смотреть короткие кандидаты.

Максимум (не более 5 вхождений «2025», оканчивается на 2025):

s = open('24.txt').readline()
m = 0
for i in range(len(s)):
    for n in range(i + m, len(s)):
        c = s[i:n + 1]
        if c.count('2025') > 5: break
        if c[-4:] == '2025': m = max(m, len(c))
print(m)

range(i + m, ...) отсекает слишком короткие подстроки: нам нужна длина больше текущего m.

Минимум: конец идёт от начала, и как только условие выполнено, запоминаем длину и выходим из внутреннего цикла.

Сначала простой случай: один проход

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

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

Почему двойной цикл не зависает

Простой перебор всех подстрок на строке из миллиона символов считался бы вечно. Его спасают две вещи:

• break обрывает внутренний цикл, как только условие нарушено. Дальше подстрока только растёт, и лучше не станет.
• range(i + m, ...) сразу пропускает подстроки короче уже найденного ответа m: они нам не нужны.

Запись s[i:n + 1] это кусок строки от i до n включительно, поэтому в конце стоит + 1.

# пиши решение здесь

Замены символов

Если несколько символов для задачи равноценны, удобно заменить их одним. Условие становится короче, а проверка проще.

Если несколько букв ведут себя одинаково, заменяем их на одну:

s = s.replace('0', 'N').replace('P', 'N')
m = 0
for i in range(len(s)):
    for n in range(i + m, len(s)):
        c = s[i:n + 1]
        if 'NN' in c: break
        m = len(c)
print(m)

Это «максимальная подстрока без двух подряд идущих N» (после замены).

# пиши решение здесь

# пиши решение здесь

Арифметические выражения

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

from re import finditer
num = r'(0|[1-9][0-9]*)'             # число без ведущих нулей
v = rf'{num}(\+{num})*'               # сумма чисел
print(max(len(x.group()) for x in finditer(v, s)))

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

Регулярное выражение читается по кускам:

Запусти на короткой строке и посмотри, что находится:

from re import finditer
s = '12+05+7++30+4'
num = r'(0|[1-9][0-9]*)'
v = rf'{num}(\+{num})*'
for x in finditer(v, s):
    print(x.group())

Окно из индексов: indexes и pop(0)

Этот приём нужен, когда просят подстроку с заданным числом вхождений. Запоминаем, где встретился образец, и держим в списке только последние k позиций.

Если условие «шаблон встречается ровно/не менее k раз, длина минимальна», двойной цикл не нужен. Идём по строке один раз и храним индексы последних k вхождений шаблона: когда их ровно k, подстрока идёт от первого индекса до конца последнего вхождения.

Код (шаблон из пяти букв, где совпадают 1-я, 3-я, 5-я и 2-я, 4-я, 170 вхождений, минимум):

s = open('24.txt').readline()
indexes = []
mn = float('inf')                                     # бесконечность
for i in range(len(s) - 4):
    if s[i] == s[i + 2] == s[i + 4] and s[i + 1] == s[i + 3]:
        indexes.append(i)
    if len(indexes) > 170:
        indexes.pop(0)                                # выкидываем самое раннее
    if len(indexes) == 170:
        start_i = indexes[0]
        end_i = indexes[-1] + 4
        mn = min(mn, end_i - start_i + 1)
print(mn)

# пиши решение здесь

Ловушки