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

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

来源

2012-01-17 alvas

你有没有经验将迭代代码转换为递归代码，对于一般情况是？ – 2012-01-17 09:30:38

nope，通常我只是简单地将'pattern'放入一个函数中并调用搜索，直到函数返回'text'的末尾。 – alvas 2012-01-17 09:34:11

好吧，你在某种程度上处于正确的轨道。这个想法是打破一个迭代解决两个或多个子问题然后用另一个递归调用来解决问题的问题。这是基本原则。 – 2012-01-17 09:38:34

当然有。如果搜索字符串中的小图案，我不会推荐使用Rabin-Karp。 KMP即Knuth-Morris-Pratt算法需要线性时间和线性附加存储器，并且可以返回所有匹配，而不会遇到与Rabin-Karp打交道时的麻烦。请阅读wiki。这个算法有点难以理解，但是对于代码来说更短，一旦你明白了，你会感到非常满意。

来源

2012-01-17 09:57:37

我试着将这个KMP模块运行到我的代码中，并最终导致内存不足问题。 http://www.fmi.uni-sofia.bg/fmi/logic/vboutchkova/sources/KMPMatch_java.html。有没有其他简单但节省内存的字符串搜索方法，我从http://johannburkard.de/software/stringsearch/尝试了BNDM，但重新编码有点过长，而且我的项目指令是保留字符串搜索简单但时间/内存不消耗。有什么建议么？ – alvas 2012-01-22 21:52:51

这样做有点麻烦 - 如果你的内存不够用于一个算法，该算法需要比输入本身多两倍的内存（或者如果该模式小于要搜索的字符串，则显着减少）。可能它更可能是你的Java虚拟机设置不好。现在我更加敦促你帮助你，因为我发现我们来自同一所大学：P – 2012-01-23 07:34:00

=）鲍里斯，你是来自台大或UdS吗？哈哈哈。我已经使Rabin-Karp递归，并且它也进入了内存不足的问题。我通过实现BNDM算法解决了这个问题。但它仍然不如我使用http://johannburkard.de/software/stringsearch/的API – alvas 2012-01-29 09:49:03

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

来源

2012-01-17 14:25:17

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

回答

相关问题