最短前綴匹配算法？

Question

給定字符串p和字符串列表查找其中p是前綴的最短字符串。

我知道蠻力的方法，但什麼是最佳方法？

例如

p = "foo bar" 
list = {"foo bar 1", 
     "foo bar foo bar", 
     "bar foo foo foo bar bar"}; 

應該返回「富吧1」

Answer 1

如果你已經有了一個搜索空間（在你的情況下，相對恆定的list），然後生成一個索引樹或其他一些合適的結構將有助於搜索了很多。維基百科開始，說明此項足夠詳細，讓你開始：

• http://en.wikipedia.org/wiki/Trie

下面是一個使用字（上述物品，其容易擴展到任何一種甚至不使用字符串的圖像-strings）：

文章提供了與其他合適的結構，這是你的情況有幫助的一些性能的比較。

請注意，如果列表發生足夠的變化，那麼與蠻力相比，此方法的回報可能會減少，或者甚至可能會導致性能下降。

Answer 2

簡單的方法，你可能已經想到的，基本上是每個合格後檢查字符串的長度。

使用僞C＃：

int length = 0, index; 
string p = "foo bar" 
string[] list = new string[]{"foo bar 1", 
    "foo bar foo bar", 
    "bar foo foo foo bar bar"}; 
for(int i = 0; i < list.Length; i++) { 
    if(list[i].Contains(p)) { 
     if(list[i].Length < length) { 
      index = i; 
      length = list[i].Length; 
     } 
    } 
} 
MessageBox.Show("The shortest one is " + list[index]); 

Answer 3

如果你需要運行一段單p那麼直接的辦法：

1. 發現在lst與p
2. 開始的所有字符串查找其中

最短

它已經是最優化了，它在時間上是O(n)，空間上是O(1)，在Python中：

shortest_with_prefix = min((s for s in lst if s.startswith(p)), key=len) 

如果有多個p，但lst是一樣的，那麼你可以進行預處理lst成前綴樹（Trie）進行多次搜索速度更快，在Python：

from pytrie import StringTrie # pip install pytrie 

trie = StringTrie.fromkeys(lst) 
shortest_with_prefix = min(trie.iterkeys(prefix=p), key=len)