Python код занимает слишком много времени для запуска

Question

Проблема, которую мне дали, состоит в том, чтобы поменять все «o» на «ko» и «k» на «ok» 1000 раз, начиная с «ok», а затем посчитать, сколько существует последовательных o.Код значительно замедляется, как только он достигает двузначных цифр, и я не уверен, что нужно сделать, чтобы реорганизовать мой код.

import string
y ="ok"
z = ""
for c in range(1000):
    for x in y:
        if str(x) == "o":
            x = x.replace("o", "ko")
            z += x
        else:
            x = x.replace("k", "ok")
            z += x
        y = z
    z = ""
    print(y,c)
y = y.replace("k", " ")
y = y.count("oo")
print (y)

Проблема с исходным кодом

После подробного разговора с другомКит получает сообщение, состоящее из одной буквы: «К».Возмущенный этим ответом с минимальными усилиями, он отвечает «ОК», на что его друг отвечает «КУК».Проницательный человек, Кит идентифицирует образец, спровоцированный его другом: последующие сообщения состоят из того, что Кит и его друг заменяют каждое «K» на «OK» и «O» на «KO».Помогите Кита найти, сколько наборов последовательных осей длины два или больше содержится в сообщении в ответе 1000.Первое сообщение «K» не считается ответом.Дайте ваш ответ мод 10 ^ 9 + 7.

Чтобы уточнить, что составляет «наборы последовательных Os длиной два или более»: KOKOOKOOOKOOOO - в этой строке три набора последовательных K длины два или более ("ОО", "ООО", "ОООО").

Answer 1

y ="ok"
for c in range(1000):
    y = y.replace('o','ko')
    y = y.replace('k','ok')
    print(y,c)

вам, возможно, не придется искать в цикле «o», а «k» replace сделает это за вас, но это займет много времени.

Answer 2

Основная проблема здесь в том, что количество букв удваивается на каждом шаге - так, скажем, на 40-м шаге есть 2 ^ 40 букв.Если каждая буква занимает один байт, это примерно терабайт букв.Конечно, по сравнению с тем, сколько места потребуется для хранения всех 1000 шагов, это лишь малая доля.Так что нет, грубое форсирование этой проблемы невозможно.

Вместо этого цель, скорее всего, признает, что паттерн - это последовательность Туэ-Морса , за исключением того, что иногда ее переворачивают.«o» и «k» соответствуют 0 или 1, это не имеет особого значения.Вы можете выполнить поиск на странице википедии, чтобы найти максимальное количество последовательных единиц в последовательности.