Regular Expression Search with Suffix Arrays

I wonder how efficient this is in the worst case. In particular, something like [02468]+ (or something similar. A discontinuous range repeated a bunch of times.)<p>I wonder how this would compete with a full suffix tree or trie - or better yet, suffix DAG, which will generally take a whole lot more time to construct but may be (much) smaller.

Oh, cool! I&#x27;ve looked into suffix trees and suffix arrays, by way of investigating how diff works. While I found suffix trees hard to understand, this is a great explanation of suffix arrays. Suffix arrays can take much less space - I&#x27;ve heard 1&#x2F;4 as much space? - than suffix trees.