0

Boyer-Moore アルゴリズムを実装して char 配列内の特定の部分文字列を検索する Java 関数を作成しました。配列内で部分文字列が見つかったすべてのインデックスのリストを返します。たとえば、検索対象の char 配列に「The Walking Dead」という語句が含まれ、パラメーターとして指定された部分文字列が「king」である場合、値 7 を含むサイズ 1 のリストが返されます。

char 配列内の完全な単語である部分文字列のインデックスのみが返されるように、この関数を変更したいと思います。したがって、前の例では空のリストが返されますが、部分文字列が "The"、"Walking"、または "Dead" に変更された場合、サイズ 1 のリストがそれぞれ値 0、4、および 12 で返されます。

Boyer-Moore アルゴリズムを使用してこの種の機能を実装することは可能ですか? これらの結果を効率的に生成できる他の文字列検索アルゴリズムはありますか?

4

3 に答える 3

3

これはあなたが望む種類の答えではないかもしれませんが、アルゴリズムの代わりに引数を変更することができます:検索文字列の最初と最後、およびターゲット文字列の最初と最後にスペースを追加します(場合最初または最後の単語がヒットです)。句読点やその他の単語以外の文字も特別に扱う必要があります。

于 2012-11-17T03:17:40.697 に答える
0

そうです、Boyer-Moore を微調整してそれを行うことができます。

  • 各「一致」の後、一致の開始位置と終了位置が単語境界にあることを確認できます。

  • 検索を "king" から "word-boundary + "king" + word-boundary' に変更します。ここで、'word-boundary' は、変更された BM が任意の単語境界文字に対して一致する疑似文字です。

  • 入力を前処理して、すべての空白、句読点などを「単語境界」を意味する特殊文字に置き換えてから、それを検索できます。

どちらが優れている可能性が高いかは、実装方法と、同じ入力テキストを繰り返し検索するかどうかによって異なります。

于 2012-11-17T03:59:04.760 に答える