java - 返回递归匹配的字符串搜索算法 - Java

Question

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);
    }
}

Answer 1

当然有。我不建议在搜索字符串中的小模式时使用 Rabin-Karp。 KMP 即 Knuth-Morris-Pratt 算法采用线性时间和线性附加内存，并且可以返回所有匹配项而不会出现冲突，这在处理 Rabin-Karp 时会很烦人。请阅读wiki为了它。这个算法有点难理解，但代码更短，一旦你做对了，你会感到非常满意。