1

Rabin-Karp 検索アルゴリズムは正常に動作していますが、再帰検索に変更する際に誰かが私を導くのを手伝ってくれますか? http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html . 例えば：

 *  **pattern:** rar
 *  **text:**    abacadabrararbracabrarararacadabrabrarbracad 
 *  **match1:**          rar               
 *  **match2:**            rar
 *  **match3:**                     rar
 *  **match4:**                       rar
 *  **match5:**                         rar
 *  **match5:**                                     rar

再帰的なテキスト一致検索のための他の高速なアルゴリズムはありますか?

解決

http://johannburkard.de/software/stringsearch/から外部ライブラリをビルド パスに追加します。以下のコードは、一致のすべての開始位置を返します。match1 や match2 などの組み込みのものも含まれます。

import com.eaio.stringsearch.BNDM;

String pattern = "rar";
String text = "abacadabrararbracabrarararacadabrabrarbracad";

// Loop through text to get starting position of matched pattern.
List<Integer> matchPoint =new ArrayList<Integer>();
int slice = -1;
while (slice<text.length()){
    slice+=1;
    com.eaio.stringsearch.BNDM result = new BNDM();
    int pos = result.searchString(text, slice, pattern);
    if (pos != -1) {
        slice = pos;
        matchPoint.add(pos);
    }
}
4

2 に答える 2

2

もちろんあります。文字列の小さなパターンを検索する場合、Rabin-Karp を使用することはお勧めしません。KMP、つまり Knuth-Morris-Pratt アルゴリズムは線形の時間と線形の追加メモリを必要とし、Rabin-Karp を扱う際に厄介な衝突を起こすことなくすべての一致を返すことができます。それについてはウィキを読んでください。このアルゴリズムは理解するのが少し難しくなりますが、コードは短くなり、正しく理解できれば非常に満足できます。

于 2012-01-17T09:57:37.757 に答える
1

より長いパターンの場合、Boyer-Moore アルゴリズムまたはHorspool のアルゴリズムのようなバリアントが一般的に高速です。Boyer-Moore アルゴリズムは、大きなアルファベットにはあまり適していません。テキストが完全な Unicode 範囲である場合、かなり大きなシフト テーブルが使用されますが、テキストが ASCII または latin1 の場合、ルックアップ テーブル用の余分なスペースは小さくなります。大きいアルファベットならKMPもオススメです。

于 2012-01-17T14:25:17.357 に答える