<p>For a fixed-length prefix, store them in a hash table.  For a variable-length prefix, use a <a href="https://en.wikipedia.org/wiki/Trie" rel="nofollow noreferrer">trie</a>.</p>

<p>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).</p>

CC BY-SA 4.0
2019-08-31T11:04:50.207Z
I cannot sort by lexicological order, because the results need to be returned according to the "importance".
Flux
CC BY-SA 4.0
2019-08-31T11:05:53.103Z
@Flux, you can store the importance with each string, then once you find all matches, sort them by importance.  There are many possibilities.  In any case, this does not appear to be a research-level question.
D.W.
CC BY-SA 4.0
2019-08-31T13:45:36.027Z
@Flux You may find this excellent video and relevant notes useful:    https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/lecture-videos/session-16-strings/
Avi Tal
CC BY-SA 4.0
2019-08-31T11:03:35.223Z
2019-08-31T11:03:35.223Z
D.W.
<p>Suppose I have a very long list of strings (millions of them), ordered by importance. For example:</p>

<pre><code>...
barracudas
oftwalj
velasp
offso
skenep
vitriolic
offscre
...
</code></pre>

<p>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 <code>of</code>, which should return <code>oftwalj</code>, <code>offso</code>, <code>offscre</code>, etc. in the order of importance.</p>

<p>Things I have used in the past to solve this problem:</p>

<ul>
<li>Linear search - eventually became too slow as the list became very large.</li>
<li>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.</li>
</ul>

<ds.data-structures>
Data structure for getting all matches of a prefix from a large list of strings
Flux
# Data structure for getting all matches of a prefix from a large list of strings

(Asked by: username_0 on 2019-08-31)

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.

**Tags:** ds.data-structures

---

## 1 answers

### Answer by username_1 on 2019-08-31. Score: 2

For a fixed-length prefix, store them in a hash table. For a variable-length prefix, use a [trie](https://en.wikipedia.org/wiki/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).

> **Comments:**
> **username_0**: I cannot sort by lexicological order, because the results need to be returned according to the "importance".  
> **username_1**: @Flux, you can store the importance with each string, then once you find all matches, sort them by importance.  There are many possibilities.  In any case, this does not appear to be a research-level question.  
> **username_2**: @Flux You may find this excellent video and relevant notes useful:    https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/lecture-videos/session-16-strings/  

---

