Question

Python Дата строка цифр. Найти закономерность(ключ), как она образована. Не обязательно полное повторение в закономерности Ключ должен быть кратчайшим из всех возможных ключей, которые могут быть использованы для кодирования сообщений, т. е. когда возможные ключи 12 , 1212, 121212, программа должна вернуть 12. Пример: 12121212121 - вернет 12 19391 - вернет 1939 19391939193 - вернет 1939

Answer 1

s = input()

k = ''; i = 0

while True:

   k += s[i]

   if len(s)%len(k) == 0:

       l = k*(len(s)//len(k))

   else:

       l = k*(len(s)//len(k)) + s[-(len(s)%len(k)): -1]

   if l == s:

       break

   else:

       i += 1

print(k)

Answer 2

Для решения этой задачи можно использовать алгоритм нахождения самого короткого повторяющегося подстроки (кратчайшего ключа) в данной строке. Один из таких алгоритмов - алгоритм Рабина-Карпа.

Алгоритм Рабина-Карпа использует хеширование для нахождения подстроки с определенным хешем, что позволяет находить повторяющиеся подстроки в строке за линейное время.

Вот Python-код для решения этой задачи:

pythonCopy code
def find_shortest_repeating_substring(s):
    n = len(s)

    def get_hash(subs):
        h = 0
        for ch in subs:
            h = (h * 256 + ord(ch)) % 101
        return h

    for length in range(1, n // 2 + 1):
        hash_set = set()
        for i in range(n - length + 1):
            substring = s[i:i+length]
            h = get_hash(substring)
            if h in hash_set:
                return substring
            hash_set.add(h)

    return s  # Если ключ не найден, возвращаем исходную строку

# Примеры
print(find_shortest_repeating_substring("12121212121"))   # Вывод: "12"
print(find_shortest_repeating_substring("19391"))         # Вывод: "1939"
print(find_shortest_repeating_substring("19391939193"))   # Вывод: "1939"

В этом коде функция find_shortest_repeating_substring принимает строку s и ищет самую короткую повторяющуюся подстроку (ключ) в ней с помощью алгоритма Рабина-Карпа. Если ключ не найден, функция вернет исходную строку.

Обратите внимание, что этот код работает эффективно для небольших строк, но может занимать много времени и ресурсов для больших строк.