On The Topic of Suffix Links in Suffix Automata
Background
For a Suffix Automaton, the suffix links form a suffix tree of the reverse string. (An example of utilizing this can be found on USACO.) To make things simple, I well henceforth refer to "suffix tree of the reverse string" as strev.
Additionally, I will use $$$s_t$$$ to represent the first $$$t$$$ characters of some arbitrary string $$$s$$$ (i.e. the prefix of $$$s$$$ with $$$t$$$ characters), $$$s[t]$$$ to represent the character at index $$$t$$$ in $$$s$$$, and $$$s'$$$ to represent the reverse of string $$$s$$$.
Observation
Since Suffix Automata can be constructed online, this means that the embedded strev is in a valid state at any given point in time, $$$t$$$, for $$$s_t$$$. This means that we can simultaneously query the suffixes of $$$s_t$$$ and the suffixes of $$$s_t'$$$ (which can be viewed as prefixes of $$$s_t$$$ if we reverse the string we are searching $$$s_t'$$$ with).
That alone is a nice property. However, there is something interesting going on here that was initially glossed over. Consider going from time $$$t$$$ to time $$$t+1$$$. The string $$$s_t$$$ grows to $$$s_{t+1}$$$ by appending character $$$s[t+1]$$$. If we look at $$$s_{t+1}'$$$, we have prepended character $$$s[t+1]$$$ to $$$s_t'$$$.
To put it simply, we now have a way to efficiently query suffixes of a string that we can prepend to online! Most other online suffix-related string algorithms are centered around appending-based operations, not prepending.
One might be quick to point out that this is not any different from reversing the string then performing most any other suffix-related string algorithm; however, note that this is not possible online. This is because characters of a string are usually given from left to right for online problems, and getting back to what I mentioned prior, reversing the string means these operations are now prepending to the string. (Using other suffix-related string algorithms would require reconstruction each time we need to prepend.)
My Questions to You All
- Is there another way to efficiently perform such operations in an online fashion? (Feel free to point out if I missed something simple or obvious; I am always open to filling in my knowledge gaps and/or correcting silly errors I have made!)
- Could this be useful for solving certain string-related problems? Assuming I didn't miss anything, would creating problems which require a similar method to what was outlined in this blog be reasonable?
- Would it be possible to construct an algorithm which supports both prepending-based and appending-based operations online?
Addendum
With the wealth of knowledge that exists out there, there is much that I do not know, so if you notice anything I have missed, seem to misunderstand, or you just want to share some other related knowledge, feel free to do so!
