Is there a way to support removal of last added character from a suffix tree or automaton?
I’ve seen couple problems on codeforces and codechef (like this) in which strings in a query are formed by extending previous strings. Thus if I could decompose the strings into something like a directed tree or spaghetti stack, it should solve it easily.
It might be possible by making the tree persistent, but since the tree by itself “contains” all the information about S[0...n-2], is it possible to retreive the older tree without persistence?