Почему работает неправильно код?

Question

Подскажите пожалуйста, в чём проблема? "Текстовый файл состоит не более чем из 1 200 000 символов X, Y, и Z. Определите максимальное количество идущих подряд символов, среди которых нет подстроки XZZY" Файл не могу загрузить.

f = open('24_3.txt').readline()
k = 1
m = 1
for i in range(1, len(f) - 1):
    if f[i] == 'X' and f[i + 1] == 'Z' and f[i + 2] == 'Z' and f[i + 3] == 'Y':
        k = 1
    else:
        k += 1
    m = max(m, k)
print(m)

Но выдаётся неправильный ответ

Answer 1

Не ответ

with open('24_3.txt', 'r', encoding='utf-8') as file:
    text = file.read()
    # В вашем случае, скорее всего, так
    # Дальше ищем последовательньности

Answer 2

Должно работать правильно:

with open('24.txt', 'r') as f:
    f = f.read()

my_list: list = list(map(len, f.split('XZZY')))
my_list[0], my_list[-1] = my_list[0] - 3, my_list[-1] - 3
print(max(my_list) + 6)

Answer 3

То что происходит в функции max_proper_substr лучше всего нарисовать:

Точками обозначены последовательности символов в которых нет комбинации XYYZ.

первая подстрока             третья подстрока
|                            | 
-------------                ------------------
..........XZZY..............XZZY............XZZY........
           --------------------              -----------
           |                                 |
           вторая подстрока                  четвёртая

Подстроки свободные от XZZY обозначены пунктирными линиями. Как видите они перекрываются. Код ниже учитывает это:

def max_proper_substr(text):
    max_length = 0
    start = 0
    while True:
        end = text.find('XZZY', start)
        if end == -1:
            length = len(text) - start
            max_length = max(max_length, length)
            break
        length = end - start + 3
        max_length = max(max_length, length)
        start = end + 1
    return max_length

Читать файл тоже надо умеючи. В хвосте файла, скорее всего будет перевод строки, который надо убрать вызовом strip. Иначе он может быть зачтён в длину последней подстроки.

with open('24_3.txt') as f:
    text = f.read().strip()

Код выше правильно решает поставленную задачу при любых входных данных. То что в ЕГЭ только один тест и строка в середине позволяет срезать угол. Я срезать угол не стану, а покажу ещё одно правильное полное решение. Идея в том чтобы разбить текст на фрагменты, а затем увеличить длину фрагментов на шесть, если они внутри, и на три, если с краю. Код правильно сработает даже если фрагмент один:

def max_proper_substr2(text):
    lengths = [len(s) for s in text.split('XZZY')]
    lengths[0] -= 3
    lengths[-1] -= 3
    return 6 + max(lengths)

P.S. Константы 3 и 6 в коде заменяются на значения зависящие от длины "запрещённой" подстроки. Оба решения можно обобщить для любых "запрещённых" подстрок. Но не всё так просто.

Упражение 1 Придумайте "запрещённую" строку для которой второе решение будет давать неправильные ответы.

Упражение 2 Покажите что первое решение работает для любых "запрещённых" строк.

БЛОГ НА HUSL

Почему работает неправильно код?

Ответы (3 шт):