Построение суффиксного дерева ACB, когда у нас уже есть суффиксное дерево AB

Недавно я столкнулся с вопросом о дереве суффиксов. Предположим, у нас уже есть суффиксное дерево для строки S=AB, т. е. S является конкатенацией префикса A и суффикса B строки S. Теперь мы хотим построить суффиксное дерево U=ACB. Каков наиболее эффективный алгоритм для этой задачи на данный момент?

Наивным способом было бы перестроить U заново, что можно сделать за время O(|U|). Но он не будет использовать никакой информации о суффиксном дереве S. Можем ли мы сделать лучше, чем O(|U|)? Может быть, O(|C|), то есть так же хорошо, как построить суффиксное дерево только из C?

Большое спасибо.


algorithm suffix-tree
person Stone    schedule 20.11.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Основываясь на поиске в Google «динамического дерева суффиксов», я думаю, что это, вероятно, область активных исследований. Я смог найти бумагу

Паоло Феррагина и Роберто Гросси, "Быстрое поэтапное редактирование текста", Материалы шестой ежегодной конференции ACM-SIAM симпозиум по дискретным алгоритмам, стр. 531-540, 1995 г.

Это не первое (или, возможно, последнее) слово в этой теме, и я только бегло просмотрел его часть, но они представляют несколько вариантов суффиксных деревьев, которые обеспечивают лучшее время при вставке, удалении или изменении строк. После вставки u-й подстроки:

  • Data structure 1
    • To find all pocc occurrences of a length-p string: O(p + pocc + u*log(p) + log n)
    • Чтобы вставить строку длины: O(s*log(n + s))
  • Data structure 2
    • To find all pocc occurrences of a length-p string: O(p*log(p) + pocc + u*(log(p) + log(n/u)))
    • Чтобы вставить строку длины: O(s*log(s) + log u)
person j_random_hacker    schedule 20.11.2014