# How to store set of long char strings to search for long char string key

I have a set of several thousand strings of max length 1024 (containing all visible ASCII chars plus space) I need to store to make it fast to search for an exact match of a key. What is the best algorithm to store the set and to search for a match?

One approach is to use a suffix array (or suffix tree). That allows very fast searching for a match.

Given multiple words, there is a standard way to compute a suffix array (or suffix tree) associated with them: concatenate them, separated by some separator. For instance, if the words are APPLE, CAT, and DOG, you obtain the string APPLE\$CAT\$DOG\\$. Then, compute the suffix array/tree of that single long string.

• According to the link you provided, a suffix array is used to find a substring of a single string. Are you suggesting I consider the set of several thousand longish strings as a single string and compute all suffixes on the set? – Dave S. Mar 31 at 21:08
• @DaveS., see edited answer. – D.W. Mar 31 at 23:01

One solution that pops to my mind is to do a hash on the strings, store the hashes in some efficient tree and the hits as a list. A suitable hash algorithm might decrease the number of actual string searches. Additionally given a good hash algorithm you might only need to check a few chars.

On second thought, there are two further things to consider when selecting algorithm.

1. What is the balance between searching, adding and deleting? I assumed that searching is a lot more common that adding/deleting.
2. Where does the strings differ? If they in average all are about the same length and all start with a few hundred characters the same in the beginning it might influence your choice.