返回遞歸匹配的字符串搜索算法 - 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

回答

相關問題