後綴樹搜索時間

Question

有誰知道下面的聲明的原因？還是有更好的網站來問這種類型的問題？任何指針，將不勝感激。

如果一個模式出現在文本（長度爲n）k次，那麼在該文本的後綴樹中搜索所有那些k次的模式將花費O（n + k）。

Answer 1

後綴樹搜索的時間長度與您正在搜索的模式的長度成正比。如果你爲密西西比建立一個後綴樹並搜索ssi。必須執行的查找將是3.時間是O（n），其中n是模式的長度。

Answer 2

根據您發現此聲明的位置，可能存在具體原因，爲什麼它在上下文中是正確的。

但是，'+ k'的通常原因僅僅是需要O（k）個額外操作來插入在返回給用戶的結果列表中找到的每個匹配項。當使用倒排文件而不是後綴樹時，這不一定是這種情況，因爲在索引中找到的倒排列表（又名發佈列表）已經是最終結果列表（至少如果我們假設（a）查詢只包含一個單一的標記，（b）反演的列表未壓縮存儲）。

但後綴樹通常（除非它是特別準備）不包含這樣的匹配列表。因此，在匹配過程中，您可以確定一條通過樹的路徑，並以某個內部節點結束從那裏開始，您必須遵循該內部節點的子樹中的所有路徑來標識指示匹配的實際位置（每個匹配一個葉節點）的葉節點，並將匹配位置插入到返回的結果列表中用戶。最後一步是花費O（k）時間。

另請注意，在內部節點的子樹中，發現以下所有路徑可能會花費大量額外時間，其中總複雜度甚至高於O（n + k）。這取決於是否有從內部節點到其子樹中的葉節點的直接指針。