Performance degradation with adversary strings #2
Description
Just occurred to me to at least add an issue about this; I discovered this bug ages ago.
What is happening is that the suffix tree building suffers performance degradation when it builds trees for particularly adversary strings. Basically very long strings with extremely frequent branching, e.g. "ABABABABABAB...". Processing time exhibits a non-linear time complexity under these conditions.
The problem lies in the handling of suffix links.
Would be great to fix this problem, but the small issue I have is that I can't understand anything neither from this algorithm anymore, nor from my 'very plain English' explanation. 😅