Поиск кратчайшего повторяющегося цикла в слове?
Я собираюсь написать функцию, которая вернет мне кратчайший период группы букв, который в конечном итоге создаст данное слово.
Например, слово abkebabkebabkeb создается повторением слова abkeb . Хотелось бы знать, насколько эффективно анализировать входное слово, чтобы получить наименьший период символов, создающих входное слово.
3 ответа
O (n) решение. Предполагается, что вся строка должна быть покрыта. Ключевое наблюдение заключается в том, что мы генерируем шаблон и тестируем его, но если мы находим по пути что-то, что не соответствует, мы должны включить всю строку, которую мы уже тестировали, чтобы нам не пришлось заново наблюдать эти символы.
def pattern(inputv):
pattern_end =0
for j in range(pattern_end+1,len(inputv)):
pattern_dex = j%(pattern_end+1)
if(inputv[pattern_dex] != inputv[j]):
pattern_end = j;
continue
if(j == len(inputv)-1):
print pattern_end
return inputv[0:pattern_end+1];
return inputv;
Я нашел решение, основанное на вашем посте, которое могло бы принять неполную схему:
(defn find-shortest-repeating [pattern string]
(if (or (empty? (clojure.string/split string (re-pattern pattern)))
(empty? (second (clojure.string/split string (re-pattern pattern)))))
pattern
(find-shortest-repeating (str pattern (nth string (count pattern))) string)))
Решение Regex:
Шаг 1: Разделите каждый символ символом-разделителем, который не является частью строки ввода, включая завершающий (т.е. ~):
(.)
$1~
Пример ввода: "abkebabkebabkeb"
Пример вывода: "a~b~k~e~b~a~b~k~e~b~a~b~k~e~b~"
Попробуйте онлайн в Retina. ( ПРИМЕЧАНИЕ: Retina - это язык программирования на основе регулярных выражений, разработанный для быстрого тестирования регулярных выражений и способный успешно конкурировать в соревнованиях по коду-гольфу . )
] Шаг 2: Используйте следующее регулярное выражение, чтобы найти самую короткую повторяющуюся подстроку (где ~ - выбранный символ-разделитель):
^(([^~]+~)*?)\1*$
$1
Объяснение:
^(([^~]+~)*?)\1*$
^ $ # Start and end, to match the entire input-string
([^~]+~) # Capture group 1: One or more non-'~' followed by a '~'
( *?) # Capture group 2: Repeated zero or more time optionally
\1* # Followed by the first capture group repeated zero or more times
$1 # Replace the entire input-string with the first capture group match
Пример ввода: "a~b~k~e~b~a~b~k~e~b~a~b~k~e~b~"
Пример вывода: "a~b~k~e~b~"
Шаг 3: Снова удалите наш символ-разделитель, чтобы получить желаемый результат.
~
<empty>
Пример ввода: "a~b~k~e~b~"
Пример вывода: "abkeb"