Текстовый файл состоит из символов P, Q, R и S. В прилагаемом файле найдите наибольшее число символов в непрерывной подпоследовательности, которая состоит из идущих подряд групп символов SQRP. При этом в начале и в конце искомой последовательности группа символов SQRP может быть неполной.
Искомая последовательность должна содержать не менее одной полной группы символов SQRP. Например, условию задачи удовлетворяют RPSQRPSQRPS, или PSQRPSQRPSQ, или SQRPSQRPSQR и т. п.
Для выполнения этого задания нужно написать программу.
Решение
Окно
🔹 Шаг 1. Читаем файл в строку s
s = open("24.txt").read()
cycle = "SQRP"
n = len(cycle)
ans = 0
📌 Читаем файл в строку s. Цикл групп — SQRP: буквы должны идти как на бесконечной ленте …SQRP SQRP SQRP…
🔹 Шаг 2. В начале и в конце искомого куска группа может быть обрезана, но…
for phase in range(n):
l = 0
📌 В начале и в конце искомого куска группа может быть обрезана, но внутри должна встретиться хотя бы одна полная SQRP — значит, длина не меньше 4.
🔹 Шаг 3. Перебираем phase от 0 до 3: это сдвиг фазы на ленте
for r in range(len(s)):
while l <= r and s[r] != cycle[(r - l + phase) % n]:
l += 1
📌 Перебираем phase от 0 до 3: это сдвиг фазы на ленте. Для каждой фазы задаём левую границу окна l и идём по r слева направо.
🔹 Шаг 4. Если s[r] не совпадает с ожидаемой буквой cycle[(r − l + phase) mod…
if r - l + 1 >= n:
ans = max(ans, r - l + 1)
📌 Если s[r] не совпадает с ожидаемой буквой cycle[(r − l + phase) mod 4], сдвигаем l вправо, пока символ на r снова подходит. Если длина окна ≥ 4, обновляем ответ.
🔹 Шаг 5. Жми RUN
print(ans)
📌 Жми RUN — в выводе будет 52 (максимальное число символов в подходящей непрерывной подпоследовательности).
✅ Ответ: 52
🔹 Полный код
s = open("24.txt").read()
cycle = "SQRP"
n = len(cycle)
ans = 0
for phase in range(n):
l = 0
for r in range(len(s)):
while l <= r and s[r] != cycle[(r - l + phase) % n]:
l += 1
if r - l + 1 >= n:
ans = max(ans, r - l + 1)
print(ans)
