输入：

1）巨大的排序的数组;

1) A huge sorted array of string SA;

2）preFIX串P;

2) A prefix string P;

输出：

第一个字符串匹配输入preFIX如有的索引。 如果不存在这样的匹配，则输出将为-1

The index of the first string matching the input prefix if any. If there is no such match, then output will be -1.

例： SA = {AB，ABD，ABDF，ABZ} P =ABD 输出应该是1（从0开始索引）。

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?

推荐答案

如果你只想做一次，使用二进制搜索，如果​​在另一方面，你需要做许多不同的prefixes但相同的字符串数组上，建立一个基数树可以是一个好主意，你已经建立的每一个眼神起来会非常快的树后。

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.