從排序的字符串數組中找到第一個前綴匹配的最有效的算法？

Question

輸入：

1）一個巨大的排序字符串SA數組;

2）前綴字符串P;

輸出：

匹配，如果任何輸入前綴第一串的索引。 如果沒有這樣的匹配，那麼輸出將是-1。

示例： SA = { 「AB」， 「ABD」， 「ABDF」， 「ABZ」} P = 「ABD」 輸出應爲1（索引從0開始）。

什麼是做這種工作最算法的方法？

Answer 1

如果你只想做一次，使用binary search，如果在另一方面，你需要做許多不同的前綴，但相同的字符串數組上，建立一個radix tree可以是一個好主意，你以後建起來的樹每個擡頭都會非常快。

Answer 2

FreeBSD內核使用Radix tree作爲它的路由表，你應該檢查一下。

Answer 3

這僅僅是一個修飾的平分搜索：

• 僅檢查儘可能多的字符的每個元素作爲在搜索字符串;和
• 如果找到匹配項，請繼續向後搜索（線性搜索或進一步的二分搜索），直至找到不匹配的結果，然後返回最後匹配結果的索引。

Answer 4

可以用線性時間使用Suffix Tree來完成。構建後綴樹需要線性時間。

Answer 5

我目前的解決方案是，而不是找到「前綴」，試圖找到一個「虛擬前綴」。

例如，前綴是「abd」，試圖找到虛擬前綴「abc（255）」。 （255）只代表最大字符數。找到「abc（255）」後。下一個單詞應該是匹配「abd」的第一個單詞（如果有的話）。

Answer 6

您是否有能力預先計算所有可能的前綴？

如果是這樣，您可以這樣做，然後使用二進制搜索在預先計算的表中查找前綴。使用前綴將下標存儲到所需的值。