Gerald's blog

By Gerald, 14 years ago, In Russian
Разбираясь с тандемными повторами при решении задачи, которую обсуждали тут, я перечитал несколько трудов Гасфилда и Крочемора (не уверен что это так пишется по русски =) ) по тандемным повторам. В основном все алгоритмы, описанные там, находят все вхождения тандемных повторов в строку (примитивных, вообще всех, различных, вариаций много). И лишь только в одной статье Гасфилда отдаленно упоминается, что существует алгоритм, который отвечает для позиции i в строке, существует ли какой-нибудь (возможно минимальный) тандемный повтор начинающийся в позиции   i - L + 1 длины L. Кто-нибудь что-нибудь слышал о подобном алгоритме, статье где его можно прочитать? Или может быть кто-нибудь знает как свести одну из вышеперечисленных решенных задач к этой за приемлемое время? 
 
P.S. Гугл скромно молчит в ответ на все вопросы :(
  • Vote: I like it
  • +20
  • Vote: I do not like it