BWTIL: a set of tools to work with BWT-based text indexes

[Nicola Prezza]

With respect to de Bruijn sequences being a worst case, I was thinking of the hypothetical hash table (due to potentially ballooning memory requirements), not your data structures.

Ah, yes you are right, probably with some hash functions de Bruijn seq represent the worst case since they present all possible combinations of input.

It's an interesting feature of text problems that the best case for one algorithm is the worst case for another and vice versa.

Totally agree

[Nicola Prezza]

The online construction for deBruijn automata probably parallels the one for suffix trees.

yap, it resembles Ukkonen's algorithm, though is much simpler: once in a state, if you read character 'c' in the text and edge labeled 'c' does not exists, then create it together with the new state. Otherwise, follow the edge.