通過後綴樹搜索模式

Question

在給定的後綴樹中搜索模式需要O（m）個時間，其中m是模式的長度。怎麼樣在文本中獲得所有模式的出現？我讀過如果有一個模式出現k次，那麼在文本中查找它們的時間複雜度就是O（m + k）。但是我無法理解這個O（+ k）時間複雜度。任何幫助！ [當然，預處理時間是O（n）：n是文本的長度]。

Answer 1

後綴樹節點下面的葉子存儲後綴索引，後綴索引以該節點中定義的前綴開頭。因此，只需在後綴樹中找到用於搜索模式匹配的節點後，計算後代樹葉即可。使用DFS可以在O（k）時間內完成k個葉子（k個匹配）。如果您只想計算出現事件的次數，那麼如果您首次使用DFS計算每個節點下面的樹葉數並將其存儲爲節點上的輔助信息作爲額外的預處理，並計算後綴樹，則可以在恆定時間內完成此操作。 （仍然O（n）時間）。