これはインタビューの質問です。
次のような Web アドレスを含むテキスト ファイルがあります。
www.yahoo.com
www.google.com
www.apple.com
www.microsoft.com
oo、goog、app などの部分文字列のリストがあります。部分文字列の 1 つに一致するすべての行を見つけるにはどうすればよいですか? この例では、次のようになります。
www.yahoo.com
www.google.com
www.apple.com
インタビュアーは、行ごとに移動して、行にサブストリングが含まれているかどうかを確認するのが好きではありませんでした。次に、トライを使用できると言いましたが、これは、部分文字列の最初の文字が行の最初の文字と一致する場合にのみ役立ちます。これは、Google での提案機能のしくみと似ています。
ありがとう
正規表現を使用できます。たとえば、式oo|goog|appはそれを行います。
非常に多くの部分文字列があり、大量のテキストを検索する場合は、Aho-Corasick 文字列一致アルゴリズムなどを使用します。
ブルート フォース アプローチ (標準の文字列マッチング アルゴリズムを使用) と Aho-Corasick アルゴリズムでは、"www.google.com" に対して 2 つの一致 ("oo" と "goog") が出力されることに注意してください。 1つだけ出力します。
質問の妥当性に関するあなたのコメントに関しては、「正しい」回答を得るためではなく、問題についてどのように考えているかを見るために設計されている可能性があります. たとえば、標準の文字列検索アルゴリズムを使用すると、MxN (M は検索する文字列の数、N は検索する部分文字列の数) に比例して時間がかかります。検索する文字列ごとに正規表現を 1 回実行するだけでよいため、正規表現ソリューションの方が高速です。Aho-Corasick アルゴリズムは、ステート マシンがすべての一致を 1 回のパスで検出するため、さらに高速です。使用するアプローチは、文字列と部分文字列の数、これを実行する頻度、ソリューションの実装に必要な時間など、多くの要因によって異なります。これ'