算法如何在大文件中搜索短語？

Question

比方說，我有一個隨機文本的大文本文件（幾MB到GB），只包含小寫字母，不包含空格。但是，有人在英文字詞的中間附加了一個字符串（僅包含小寫字母，沒有空格）。

由於我不知道字符串應該說什麼（只有它是英文的，而不是完全隨機的文本），我該如何去查找字符串是什麼以及它說什麼？我可以使用英文單詞詞典。

Answer 1

將字典構建到trie中並遍歷文件。 O（n）文件的大小（在最壞的情況下我相信O（文件大小*特里深度））和O（1）內存（固定字典的大小並假設最小的最大單詞）。這也是可流動的，並且非常具有內存效率，因此可以擴展到只有千兆字節RAM的TB級數據。