минимальная циклическая подстрока в большей циклической строке

Question

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

Циклическая строка будет определяться как соединение двух или более одинаковых строк, например"abababab" или "aaaa" ...

Теперь в заданной, например, строке T = "abbcabbcabbcabbc" есть цикл шаблона "abbc", но самой короткой циклической подстрокой будет "bb».

Answer 1

Если вы просто ищете подстроку, которая появляется более одного раза:

Создайте Дерево суффиксов из строки.

При создании дерева суффиксов вы можете рассчитывать повторения каждой подстроки и сохранять их по количеству вхождений на узле.

Затем просто выполните BFS-поиск по дереву (что даст вам многоуровневый поиск от коротких до длинных строк) и найдите первую подстроку, которая длиннеечем 1, что встречалось более одного раза.

Общая сложность: O (n) , где n - длина строки

Редактировать:

Пути от корня к листьям имеют взаимно-однозначное отношение с суффиксами S

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

Вот суффиксное дерево банана, где каждый узел содержит одну букву, вы можете видеть, что у вас есть все подстроки там.

Если вы посмотрите на раздел application дерева суффиксов, вы увидите, что оно используется именно для такого рода задач - поиска информации о подстроках.

Посмотрите на изображение из корня, вы можетесм. ВСЕ подстроки начинаются с корня (список BFS):

b
a
n
ba
an
na
ban
ana
nan
bana
anan
nana
banan
anana
banana

Answer 2

Позвольте мне вызвать «abbc» генератор в вашем примере - то есть строку, которую вы повторяете, чтобы получить большую строку.

Самое первое наблюдение состоит в том, что меньшая строка должна быть сделана повторением некоторой подстроки дважды.

Понятно, что наименьшая строка должна быть меньше генератора, повторяемого дважды (генератор 2 *), потому что генератор 2 * циклический.

Теперь обратите внимание, что вам нужно учитывать только строку, полученную при взятии генератора 3 раза, при поиске циклической строки меньшего размера. Действительно, если самого маленького нет, но оно есть в генераторе 4 *, то оно должно охватывать как минимум два генератора, но тогда оно не будет самым маленьким.

Итак, теперь давайте предположим, что большая строка - генератор 3 * (или генератор 2 *). Также ясно, что если генератор имеет только разные цифры, то ответ - генератор 2 *. Если нет, то вам просто нужно найти все пары одинаковых символов в большей строке, скажем, в позициях i и j и проверить, является ли строка, начинающаяся с i, длиной 2 * (j-i), циклической. Если вы попробуете их в порядке увеличения j-i, вы можете остановиться после первого успеха.