用於從一大組字符串中搜索「字符串」的高效數據結構

Question

我們都知道Google自動完成功能。鍵入「an」並獲得以「an」開頭的可能結果，例如「動物」。你可以想象前綴樹（trie）如何適用於此。

但是，如果你想匹配「是在字符串」而不是「開始於」。系統效率低下。

一個可怕的解決辦法是：

• 獲取的可能性，所有的可能性循環，
• 只保留那些INSTR（可能性，令牌）==真

Answer 1

Generalized suffix tree是什麼您正在尋找。

維基百科：

它可以建在O(n)時間和空間，可以用來查找所有z出現的字符串長度m的P的O(m+z)時間