文字列パターン検索アルゴリズムスタックオーバーフロー

Question

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[]は、サンプルコードと同じです。私の質問は以下のとおりです。

1. 引数のテキスト文字列が大きくなっている、以上の2200個の文字が、それは常にjava.lang.StackOverflowErrorを上げたと言います。具体的には括弧の中の3つのアスタリスクの行にある。 ans.add(n-d)しか残っていなくても、同じ問題が残っています。戻り値booleanは意味がありません。たとえ関数returnの型をvoidに変更して最後の行を削除しても、それは同じ問題です。

2. これを行うには良い方法はありますか？

Answer 1

現在、JVM（Hotspot）にはテールコールの最適化機能はありません。したがって、各再帰はスタックを消費します。だからあなたはstackoverflowエラーを取得します。現時点では、反復的なアプローチに固執する方がよいでしょう。