高效過濾文本字符串中的單詞

Question

當人們將文本輸入到文本字段中時，在將其添加到文本框（用於聊天）之前，有一些單詞是我想要查找和過濾的。這包括如果他們不是空間拼接的例子太空船的字空間。

什麼樣的算法通常用於這種目的？

唯一的算法，我可以在文本每個字想迭代的：

for each word to filter 
for each char in string 
if the substring from index of the first letter of word to the current index == word, do something with the word 
end for each 
end for each 

是否還有更好的，更多的O（n）的方式做到這一點？

感謝

Answer 1

Tries可用於幾乎正是這個問題。

Answer 2

什麼樣的算法通常用於這種目的？

正則表達式。如果使用RE2，則會得到最差情況的O（n）匹配。你會想匹配的東西，如(space ?ship|chocolate ?mousse)等

Answer 3

基本上你試圖搜索目標字符串中的一組輸入字符串。您可以使用這些算法

1. Rabin–Karp algorithm
2. Aho–Corasick string matching algorithm

但是爲了保持與用戶的打字速度的簡單的正則表達式替換也會做。