Как удалить подстроку из дерева суффикса?

Question

Я просмотрел много литературы, но я не нашел никакой информации об удалении или вставке подстроки в дерево суффикса. Существуют только алгоритмы Ukkonen или McCreight для построения дерева.
Самый плохой способ - восстановить дерево после удаления или вставки подстроки. Но я думаю, что существует лучший способ сделать это.
Например,
У меня есть дерево суффиксов с «abcdef», и мне нужно удалить символы от 1 до 3. И тогда у меня будет дерево суффиксов с «aef». И тогда мне нужно добавить из строки 1 строки «как». И после этого у меня будет суффиксное дерево с «aasef». Вы можете мне помочь?

Answer 1

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

Что вам нужно, это две вещи: сначала «суффикс-массив», это даст вам больше контроля над поиском символов и их местоположением, во-вторых, «алгоритм кеша», это поможет вам с заменой.

Answer 2

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

«ABCDEF» является действительно тривиальным дерево суффиксов:

abcdef 
├a..$ 
├b..$ 
├c..$ 
├d..$ 
├e..$ 
└f$ 

Добавление «г» в конце или вычеркивания «а» в начале невероятно легко.

Но сказать, что мы засунуть другой «а» в середине:

abcadef 
├a 
│├b..$ 
│└d..$ 
├b 
├c 
├... 

Мы должны вернуться и проверить каждую букву с самого начала, чтобы увидеть, если нам нужно вставить узел, основанный на этом. То же самое, если у нас есть характер с конца:

abafef 
├a 
│├bafef$ 
│└fef$ 
├bafef$ 
├f 
│├ef$ 
│└$ 
└ef$ 

Если теперь вставить что-то вроде «эф» до конца, вам придется пройти и добавлять новые узлы повсюду!

Вставка символа выглядит так, как будто это потребует повторного изучения каждого символа в строке, т. Е. Линейного времени. Поскольку алгоритм Укконена уже принимает линейное время, не стоит использовать какой-либо динамический алгоритм вставки, вы должны просто регенерировать дерево с нуля каждый раз с уверенностью, что это все еще довольно хорошо.

Если вам небезразлично пространство, вы всегда можете кэшировать каждый шаг алгоритма генерации дерева, а затем, когда наступает время для вставки или удаления в точке x, просто загрузите дерево как построенное до точки x ,