Search algorithms – What is an efficient data structure for prefix matching?

I'm looking for a data structure that supports efficient random prefix matching queries (template) against a previously known set of words (dictionary). The dictionary should contain about 10,000 words of different lengths (I did not calculate the average length of words, but I do not think a word has more than 80 characters). The prefix match in this case would be equivalent to words[i].toLowerCase (). startsWith (pattern.toLowerCase ()).

A choice is obvious and allows a linear temporal search corresponding to the length of the pattern. However, I do not know if a suffix tree or an array of suffixes could make improvements over a Trie. It seems like a suffix is ​​what is commonly used for a text, not several. I also have no obligation to support various interesting use cases (longer common prefix, or number of occurrences of a prefix, etc.) that a suffix can support it effectively.

I am looking for a recommendation on which data structure to use and why. Attempts use a lot of space, and if I end up using one, I would consider compressing branches with nodes with outdegree 1.

For the happy reader double-button reader, I read this and this question, none seemed directly relevant.


Dictionary: [banana, apple, banter, orange]

Reason: prohibition
Back: banana (any match)

Reason: Grapes
Back: null