查找與查詢匹配的所有名稱：如何使用後綴樹？

Question

問題：你有一部智能手機，你打開了聯繫人應用程序。你想搜索一個聯繫人。比方說manmohan。但你不記得他的全名。你只記得mohan，所以你開始打字。當你輸入'm'時，聯繫人應用程序將開始搜索具有字母'm'的聯繫人。假設您在聯繫人列表("manmohan", "manoj", "raghav","dinesh", "aman")中存儲了姓名，現在聯繫人將顯示manmohan,manoj and aman。現在你輸入的下一個字符是'''（直到現在你已經鍵入「mo」）現在結果應該是「man mo han」。你將如何實現這樣的數據結構？

我的方法是應用KMP，因爲您在所有可用聯繫人中查找模式「m」，然後選擇「mo」。然後顯示匹配的字符串。但採訪者說這不是有效的。 （我想不出有什麼更好的辦法。）在離開之前他說有一個算法可以幫助。如果你知道它，你可以解決它。我做不到。 （在離開之前我問了那個標準算法。訪問者說：後綴樹）。任何人都可以解釋請問，它是如何更好？或者哪個是實現這種數據結構的最佳算法。

Answer 1

你試圖解決的問題基本上歸結爲以下幾點：給定一個固定的字符串集合和一個只通過追加更改的字符串，如何有效地找到包含該模式的所有字符串作爲子字符串？

在字符串上有一個簡潔的結果，對於涉及到子字符串搜索的問題通常很有用：字符串P是字符串T的子字符串當且僅當P是至少一個T後綴的前綴。你是否明白了爲什麼？）

所以想象一下，你把你的銀行中的每個名字，並構造所有銀行的所有單詞的後綴的字典。現在，給定要搜索的模式字符串P，沿着字符串走，讀取P的字符。如果你脫離了字符串，那麼字符串P不能是任何名字庫的子字符串（否則，它應該是T中一個字符串的至少一個後綴的前綴）。否則，你在某個特洛伊節點。然後，以當前訪問的節點爲根的子樹中的所有後綴對應於T中所有名稱中的子字符串的所有匹配項，您可以通過DFS找到該子項並記錄所有後綴找。

後綴樹本質上是一種時間和空間高效的數據結構，用於表示字符串集合中所有後綴的樹狀結構。它可以在時間上與T中的總字符數成比例地構建（儘管這樣做的算法很難直觀和編碼），並且被設計爲使得您可以找到根植於給定節點時間O（k），其中k是匹配的數量。

回顧一下，這裏的核心思想是對T中所有字符串的後綴進行排序，然後使用模式P對其進行排序。對於時間和空間效率，您可以使用後綴樹而不是後綴trie。