How to remove substring from suffix tree?

Question

I reviewed a lot of literature, but I dont found any information about deleting or insertion substrings into suffix tree. There are only Ukkonen's or McCreight's algorithms for building tree.
The poorest way is to rebuild tree after deleting or inserting a substring. But I think that exists a best way to do it.
For example (positions are counted from 0):
I have suffix tree with "abcdef" and I need to delete symbols from 1 to 3. And then I will have suffix tree with "aef". And then I need to add from position 1 string "as". And after this I will have suffix tree with "aasef". Can you help me?

Answer 1

you are mixing two tasks in your question, first search for the character, second replace the character. Suffix tree does the first part search the character for you, now you need a second algorithm to replace that character with new character. As the characters are replaced the original suffix tree become invalid, so the tree has to be mapped again to do a second replacement.

What you need is two things, first "suffix array" this will give you more control over searching for characters and their location, second is the "cache algorithm" this will help you with replacement.