I understand, thank you. (Though a lot of inexact pattern matching is done with using exact pattern matching of substrings with the pidgeonhole principle.) Tri

I understand, thank you. (Though a lot of inexact pattern matching is done with using exact pattern matching of substrings with the pidgeonhole principle.) Tries led to suffix trees led to suffix arrays led to Burrows-Wheeler transform led to FM index, which is probably the best way to do an offline search. If you haven't looked at BWT indexing, it's worth at least checking out. It preserves the advantages you speak of with linear memory cost with the search space. It's a lot more hairy to implement, unfortunately.