Короткий код для задачи №24 (поиск короткой подстроки)

Код в конце статьи)

Задача с сайта Полякова К.Ю.

В первую очередь скачиваете текстовый файлик в определенную папку и в эту же папку нужно сохранить файл python

должно быть так

далее копируем название файла (если вы сохранили просто 24.txt, то можно не заморачиваться и просто вписать в код вручную) полностью с расширением (это архиважно). Если нет расширения - нужно включить

в вин10 - вид - расширения значков, в вин11 вот так

далее открываем текстовый файл в python функцией open(), и проверяем, нет ли ошибок

run - run module , если нет ошибки - приступаем к решению

самое главное в 24 задании: весть текст - это одна длинная строка...

это значит, что смело применяем  метод readline(), и посмотрим как выводится часть строки - выведем первые 100 символов из любопытства

сразу приходит здравая мысль, как найти количество вхождений (простой и добрый вложенный цикл, но, думаю, выполняться будет 100 лет...)

и тут вспоминаем математику: 

ведь если хитростью создать список чередующихся элементов RSQ и строк разной длины, то вложенный цикл уже будет бодрее работать. Как делать списки из строки - метод strip(). Остается загвоздка, если есть вот такая строка RSQRSQ. Тут нужен тоже между элементами пустой элемент списка. 

А что, если заменять 'RSQ' на '*RSQ*' и потом методом split() по звёздочке разбить строку на список. Как раз получится то, что мы и хотим: список из чередующихся элементов.

Выполним это и посмотрим первые 20 элементов

как раз то, что мы и искали. Теперь, как сказал один мой ученик, представьте забор: штакетник и прогалы между штакетинами)) - если ищем 130 штакетин, сколько будет элементов вместе с прогалами? (забор четкий, без косяков)

Правильно, 130 + 129 = 259

Далее в курсе будут задачи на поиск максимальной подстроки, обратите внимание, там ищем другим способом.

Это было маленькое отступление. Но, важное!

В нашей задаче ищем подряд идущие 259 элементов списка. Проверяем сумму их длин. Находим самую короткую и все))

Помните!!! Если мы начали с простого текста, то range() начинаем не с 0, а с 1. И чередуем через 2 элемента. 

В задаче условие тоже не простое: нельзя брать подстроку, которая заканчивается на Q

Значит вводим переменную для проверки элемента f[i + 260] и на всякий случай f[i + 261]

Значит ответ 496 + 1 = 497

Код Python:

f = open('24-357.txt').readline().replace('RSQ', '*RSQ*').split('*')

mn = 10 ** 10 # просто рандомное огромное число
fnext = ''
for i in range(1, len(f) - 259, 2):
    sm = sum([len(x) for x in f[i:i + 259]])
    if sm < mn:
        mn = sm
        fnext = f[i + 260] + f[i + 261]
        

print(mn, fnext)