Эффективная фильтрация слов в текстовой строке

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

Попытки могут быть использованы практически для решения этой проблемы.

Answer 2

В основном вы пытаетесь найти набор входных строк в целевой строке. Вы можете использовать эти алгоритмы

1. алгоритм Рабина-Карпа
2. Алгоритм совпадения строк Ахо-Корасика

Но чтобы сохранить скорость набора текста, подойдет и простая замена регулярного выражения.

Answer 3

Какой тип алгоритма обычно используется для такого рода целей?

Регулярные выражения.Если вы используете RE2 , вы получите совпадение O ( n ) в худшем случае.Вы будете хотеть соответствовать для вещей как (space ?ship|chocolate ?mousse), и т. Д.