Алгоритм поиска двойных подслов данного слова

Question

Подслово U данного слова V является двойным, когда оно имеет форму u = ww, например, «abab» является двойным подсловом слова «acdababx», а «cdab» - нет.

Мне нужен алгоритм, который проверяет, является ли данное подслово U слова V двойным. V может быть предварительно обработан за линейное время, но ответ для любого конкретного U должен иметь постоянную сложность по времени, потому что будет много U для каждого V. U задается как интервал, например, если V = "acdababx", интервал [3..6] соответствует подслову "даба".

пример ввода и вывода:

V = abbacbacca

U =

• [1 4] -> Нет
• [3 8] -> Да
• [5 8] -> Нет
• [8 9] -> Да
• [1 10] -> Нет

Это не проблема для любого текущего конкурса.

Answer 1

Вот один алгоритм, который утверждает, что отмечает конечные точки всех двойных слов (или, как это широко известно в литературе, тандемные повторы) в дереве суффиксов входного слова (которое может быть построено в O (n))время.Конечно, поскольку у меня нет полного доступа к статье, я не уверен, что она удовлетворит время запроса O (1).

Статья: Алгоритмы линейного времени для поиска ипредставляющих все тандемные повторы в строке

Надеюсь, это поможет.