Rabin-Karp検索アルゴリズムはうまくいきますが、誰でも再帰検索に変更する際の手引きはありますか? http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html。 例:再帰的一致を返す文字列検索アルゴリズム - Java
* **pattern:** rar
* **text:** abacadabrararbracabrarararacadabrabrarbracad
* **match1:** rar
* **match2:** rar
* **match3:** rar
* **match4:** rar
* **match5:** rar
* **match5:** rar
再帰的なテキストマッチング検索のアルゴリズムは他に高速ですか?
SOLUTION
パスを構築するために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);
}
}
反復コードを再帰的コードに変換した経験がありますか? –
いいえ、通常は単に 'pattern'を関数に入れて、関数が' text'の最後に返答するまで検索を呼び出します。 – alvas
まあ、あなたは正しい軌道にいるのです。アイデアは、ある反復が2つ以上のサブ問題に解決し、次に別の再帰呼び出しでそれらを解決するという問題を解くことです。それが基本原則です。 –