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 时出现的冲突。请阅读wiki。这个算法有点难理解，但代码更短，一旦你做对了，你会感到非常满意。

于 2012-01-17T09:57:37.757 回答
1

对于较长的模式，Boyer-Moore 算法或类似Horspool 算法的变体通常更快。Boyer-Moore 算法并不是特别适合大字母表。如果文本可以是完整的 Unicode 范围，它将使用一个相当大的移位表，但如果文本是 ASCII 或 latin1，则查找表的额外空间很小。对于大字母，我也推荐 KMP。

于 2012-01-17T14:25:17.357 回答