要件
- 現在、1万を超えるキーワードまたは文章を含むリストがあります(数はNです)
- 入力は長い文字列で、長さは L
質問: 文字列に、与えられたリストのキーワードまたは文章が含まれているかどうかを確認してください
質問はwikipediaの単語フィルターとして説明できますが、そのページにはアルゴリズムが見つかりませんでした。この問題を解決する最も簡単な方法は、すべてのキーワードまたは文をイテレータし、長いテキストにそのような部分文字列が含まれているかどうかを毎回確認することです。キーワードが多いため、テキストが長いことを考えると、パフォーマンスは非常に悪いです。O(NL)時間を使用します
より良い解決策は O(L) で終了する必要があるようです。誰かがこれについて何か提案をすることができますか?