字符串模式搜索算法堆棧溢出

我試圖將this code修改爲遞歸版本以便執行時間效率。代碼的作用是在Text中查找所有模式的第一個索引，並將它們添加到ArrayList中。我的代碼如下：字符串模式搜索算法堆棧溢出

public boolean search(String text, int n, String pattern, int d) { 
    if (n > text.length() || n < d) return true; 
    while (d >= 0 && d < pattern.length() && n < text.length() && text.charAt(n) != pattern.charAt(d)) d = next[d]; 
    if (d == pattern.length()) { 
    (***) if (ans == null || !ans.contains(n-d)) ans.add(n-d);      
      n = n-d; 
      d = -1; 
    } 
    if(n < text.length() && n >= d) search(text, n+1, pattern, d+1); 
    return false; 
}

for循環版本的我的代碼：

public void search(String text) { 
int m = this.pattern.length(); 
int n = text.length(); 
int i, j; 
for (i = 0, j = 0; i < n && j < m; i++) { 
    while (j >= 0 && text.charAt(i) != this.pattern.charAt(j)) { 
     j = next[j]; 
    } 
    j++; 
    if (j >= m) { 
    if (ans == null || !ans.contains(i-m+1)) ans.add(i-m+1);  
     j = 0; 
     i = i - m + 1; 
    } 
}}

對於最壞的情況下，它的指數，這就是爲什麼我不能滿足時間限制。

數組next[]與示例代碼相同。我的問題是：

當參數文本字符串越來越大，說超過2200個字符，它總是提出一個java.lang.StackOverflowError;特別是在括號內的三個星號的行中。即使只剩下ans.add(n-d)，仍然是同樣的問題。返回值boolean是毫無意義的，即使我將功能return類型更改爲void並刪除最後一行，仍然是同樣的問題。
有沒有更好的方法來做到這一點？

來源

2016-12-14 Tao Wang

是什麼讓你認爲遞歸版本更高效？它所能做的都比較慢。正如消息所述，您會遇到堆棧溢出（因爲遞歸很大）。你最好保留原來的代碼。 –

感謝Yves Daoust的迴應。通過使用最後的第二個條件，我不必一直走到字符串結束處並在n

原始代碼的問題之一是它總是超過時間限制，另一個是它只能得到一個模式索引，我需要的是在文本中查找所有模式的索引。 –

當前JVM（熱點）沒有尾部呼叫優化。所以每個遞歸都會消耗堆棧。所以你得到stackoverflow錯誤。目前最好堅持迭代方法。

來源

2016-12-14 18:36:41 boring

字符串模式搜索算法堆棧溢出

回答

相關問題