高效的算法來找出一組比賽的短文本

Question

輸入：

1. 一個相對較短（100-1000字，通常情況下）的文本。
2. 預先給出約5000個表達式的固定列表，其中大多數表達式長達10-20個字符，其中一些表達式包含其他表達式（例如「嘗試」和「再試一次」）。

注意 - 只有第一個輸入發生變化，第二個輸入發生變化，並且可用於預處理。

所需的輸出：

識別表情的所有比賽，從第2項裏面的文字。如果匹配含糊不清，儘可能採取貪婪的匹配。

運行時間應該比較快，雖然沒有嚴格的性能要求。這裏的暴力嘗試可能就足夠了。

什麼是一個好的算法呢？這裏的後綴樹是否有用？如何查看所有表達式並將其放入散列表？還請注意，我對實用解決方案感興趣，因此易於實現可能比超高效算法更有用...

Answer 1

請看Aho–Corasick算法。

Answer 2

假設存儲空間不受限制的一般「算法」，用於優化此操作是基於字符構建數據樹，使您可以遞歸搜索您的模式。在構建樹索引時，向下遍歷，直到達到「唯一」點，「葉」給出該唯一事件發生位置。

在上面的段落中，例如單詞「index」出現一次。如果樹一次構建一個字符，那麼我們遵循的樹路徑將以「我」字符開始，然後「開始」。如果區分大小寫，則只有3次出現（假設，優化和索引）。當我們接下來搜索'd'時，我們遇到了獨特的結果。當然，我們可以先從空間開始我們的搜索，然後是我然後是n，我們會沿着不同的路線前進。

您也可以使樹不區分大小寫，並且您可以在每個分支點使用「nybble」而不是字節。