algorithm - 文字列検索アルゴリズム

Question

2つの文字列検索アルゴリズムの場合：KMPと接尾辞木。どちらの場合に優先されますか？いくつかの実用的な例を挙げてください。

Answer 1

「針は干し草の山にありますか？」などの多くの質問に答える必要がある場合は、接尾辞木の方が適しています。KMPは、別の単一の文字列で1つの文字列を検索するだけでよく、何度も検索する必要がない場合に適しています。

接尾辞木ははるかに一般的なデータ構造であるため、それを使用してさらに多くのことを実行できます。ここでそれを使って何ができるかを見てください。KMPは、ある文字列が別の文字列の部分文字列であるかどうかを確認するのに役立ちます。

ボイヤームーア文字、ラビンカープ文字、さらにはナイーブアルゴリズムなど、他のアルゴリズムよりも優れている状況（入力）があるため、他のアルゴリズムも確認することをお勧めします。

結論は次のとおりです。

1. 上記のようなクエリがたくさんある場合は、接尾辞ツリーを作成して、各クエリにすばやく答える価値があります。
2. これらの種類のクエリ以上のことを行う必要がある場合は、接尾辞木も作成する価値があります。
3. 文字列が別の文字列のサブ文字列であるかどうかをたまに見つけるだけでよい場合は、KMPを使用してください。