What data structure to use for indexing data for partial %infix% searching?

Question

Imagine you have a huge cache of data that is to be searched through by 4 ways :

1. exact match
2. prefix%
3. %suffix
4. %infix%

I'm using Trie for the first 3 types of searching, but I can't figure out how to approach the fourth one other than sequential processing of huge array of elements.

Answer 1

If your dataset is huge cosider using a search platform like Apache Solr so that you dont end up in a performance mess.