Data structure for getting all matches of a prefix from a large list of strings Suppose I have a very long list of strings (millions of them), ordered by importance. For example:

...
barracudas
oftwalj
velasp
offso
skenep
vitriolic
offscre
...


What is an appropriate data structure for storing this data to make it efficient to obtain all matches of any prefix? For example, I may want to search for the prefix of, which should return oftwalj, offso, offscre, etc. in the order of importance.

Things I have used in the past to solve this problem:


Linear search - eventually became too slow as the list became very large.
Storing the data in a simple hash table, where the key is the prefix, and the value is the list of words matching the prefix together with their "importance score" - this works, but the space requirement is high.
For a fixed-length prefix, store them in a hash table.  For a variable-length prefix, use a trie.

If you have a static list and don't need to support insertions or deletions into the list, storing them in sorted order by lexicographic order also works, as you can use binary search to find the matches (they will all be consecutive).