Задание EGEINF737070: Обработка текстового файла

Решение.
Считываем исходный текстовый файл одной строкой и убираем завершающий перевод строки. Получаем 10000000 символов. Порядок символов менять нельзя: требуется непрерывный фрагмент исходного текста.
Корректное число имеет вид 0 либо начинается с ненулевой цифры и продолжается цифрами. Выражение состоит из такого числа и нуля или более повторений «знак операции, число». Поэтому оно начинается и заканчивается цифрой, не содержит двух соседних операций и многозначных чисел с первым нулём. Вычислять значение выражения не требуется: неотрицательными должны быть сами числа в записи.
Обрабатываем символы слева направо. Храним три длины фрагментов, заканчивающихся в текущей позиции: z — правильное выражение с последним числом 0; p — правильное выражение с последним положительным числом; op — правильное выражение, после которого записан один знак операции. Значение 0 означает, что фрагмента такого вида нет.
Если очередная цифра равна 0, можно начать новое односимвольное число или поставить 0 после op. Это даёт новое z. К положительному числу ноль приписывать можно, поэтому p увеличивается на единицу, если такое состояние существовало. К отдельному числу 0 приписывать цифру нельзя.
Если цифра ненулевая, новое p — максимум трёх возможностей: начать число с этой цифры, продолжить прежнее положительное число или начать число после операции. Старое z продолжать цифрой нельзя из-за ведущего нуля. Состояния z и op обнуляются.
Если встретился знак операции, он допустим только после законченного числа: op равняется единице плюс максимум прежних z и p. Если обоих состояний не было, op тоже равен нулю. После операции законченного выражения пока нет, поэтому z и p обнуляются.
Будущее продолжение зависит только от вида состояния. Из двух фрагментов одного вида достаточно сохранить более длинный: любое допустимое продолжение пригодно для обоих и сохраняет разность длин. По индукции эти переходы находят самые длинные фрагменты каждого вида в каждой позиции.
В ответ берём максимум z и p по всем позициям. Состояние op не участвует, потому что выражение не может заканчиваться операцией. Все способы начать, продолжить и закончить выражение рассмотрены, следовательно, более длинный допустимый фрагмент не пропущен.
Сохраните скачанный файл рядом с программой под исходным именем. Программа на Python:

with open("img1_1786621776.txt") as f:
    s = f.read().strip()
z = p = op = best = 0
for c in s:
    if c == '0':
        z = op + 1 if op else 1
        p = p + 1 if p else 0
        op = 0
    elif c.isdigit():
        p = max(1, p + 1 if p else 0, op + 1 if op else 0)
        z = op = 0
    else:
        number = max(z, p)
        op = number + 1 if number else 0
        z = p = 0
    best = max(best, z, p)
print(best)

Для исходного файла best = 933.
Проверка: один достигающий фрагмент расположен на позициях 612010–612942 при нумерации от единицы. Его длина равна 612942 − 612010 + 1 = 933.
Начало этого фрагмента: «341440124203102431-13232333034»; конец: «0441141044241134434242111234-0». Весь фрагмент независимо разобран как чередование чисел и операций: ведущих нулей и соседних операций нет.
Независимый поиск по грамматике допустимого выражения дал ту же длину и те же границы. На всех строках длины до восьми над алфавитом 0, 1, −, * результат дополнительно сравнен с полным перебором всех подстрок.
Алгоритм выполняет постоянное число действий на каждый символ: время O(n), дополнительная память для состояний O(1), а считанная строка занимает O(n).
Ответ: 933.