テキストの文字列内の単語の効率的なフィルタリング

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

基本的に、ターゲット文字列の入力文字列のセットを検索しようとしています。あなたはこれらのアルゴリズム

Rabin–Karp algorithm

Aho–Corasick string matching algorithm

1. を使用することができますしかし、またやるだろう置き換えるユーザーのタイピング速度に簡単な正規表現を維持します。