The Most Efficient Algorithm to Find First Prefix-Match From a Sorted String Array?
Solution 1
If you only want to do this once, use binary search, if on the other hand you need to do it for many different prefixes but on the same string array, building a radix tree can be a good idea, after you've built the tree each look up will be very fast.
Solution 2
It can be done in linear time using a Suffix Tree. Building the suffix tree takes linear time.
Solution 3
This is just a modified bisection search:
- Only check as many characters in each element as are in the search string; and
- If you find a match, keep searching backwards (either linearly or by further bisection searches) until you find a non-matching result and then return the index of the last matching result.
Morgan Cheng
I am a software engineer in China. This is my Blog ??????????,??????
Updated on June 12, 2022Comments
-
Morgan Cheng almost 2 years
Input:
1) A huge sorted array of string SA;
2) A prefix string P;
Output:
The index of the first string matching the input prefix if any. If there is no such match, then output will be -1.
Example:
SA = {"ab", "abd", "abdf", "abz"} P = "abd"
The output should be 1 (index starting from 0).
What's the most algorithm way to do this kind of job?