最長リピートシーケンスではなく最大リピートシーケンス

Question

文字列の中で最も連続した文字列を取得しようとしています。たとえば ：

入力：

s = "abccbaabccba" 

出力：

2 

私は繰り返しシーケンスを把握するために、動的プログラミングを使用しているが、これは最長の繰り返し文字列を返します。 。たとえば：

入力：

s = "abcabcabcabc" 

出力：

2 
2(abcabc,abcabc) instead of 4(abc,abc,abc,abc) 

ここでは、私はDPテーブルを充填し、繰り返しシーケンスを抽出していたコードの一部です。誰も私がどのように最も反復配列を得ることができるかを提案することはできますか？

//Run through the string and fill the DP table. 
     char[] chars = s.toCharArray(); 
     for(int i = 1; i <= length; i++){ 
      for(int j = 1; j <= length; j++){ 
       if(chars[i-1] == chars[j-1] && Math.abs(i-j) > table[i-1][j-1]){ 
        table[i][j] = table[i-1][j-1] + 1; 
        if(table[i][j] > max_length_sub){ 
         max_length_sub = table[i][j]; 
         array_index = Math.min(i, j); 
        } 
       }else{ 
        table[i][j] = 0; 
       } 
      }    
     }  
     //Check if there was a repeating sequence and return the number of times it occurred. 
     if(max_length_sub > 0){ 
      String temp = s; 
      String subSeq = ""; 
      for(int i = (array_index - max_length_sub); i< max_length_sub; i++){ 
       subSeq = subSeq + s.charAt(i); 
      } 
      System.out.println(subSeq); 
      Pattern pattern = Pattern.compile(subSeq); 
      Matcher matcher = pattern.matcher(s); 
      int count = 0; 
      while (matcher.find()) 
       count++; 

      // To find left overs - doesn't seem to matter 
      String[] splits = temp.split(subSeq); 
      if (splits.length == 0){ 
       return count; 
      }else{ 
       return 0; 
      } 
     } 

Answer 1

シンプルでダンプ、考慮すべき最小のシーケンスは文字（*）のペアです：文字列全体にわたる

• ループforを使用してのように、文字のすべての連続したペアを取得文字を取得するにはsubstringです。
• 文字列内のそのペアの出現をカウントし、を使用してindexof(String, int)または正規表現を使用して作成します。そして
• ストア最大数、実際のカウントが大きいかどうかを確認するために、1つの可変ループ外maxCountとifを使用する（またはMath.max()）

（*）「ABC」は「より、5回発生した場合"ab"と "bc"だけを検索すれば十分ですので、 "abc"を確認する必要はありません。

を編集するには、以下を参照してください。コメント、要約：

• 最初の文字は文字列全体にわたって繰り返される場合は、チェック、そうでない場合は

• チェック2つの初期の文字はすべて何度も繰り返されている場合、そうでない場合

• チェック3 ...

場合

少なくとも2つのカウンタ/ループが必要です.1つはテストする文字数、もう1つはテストする位置です。いくつかの算術演算を使用してパフォーマンスを向上させることができます。文字列の長さは、剰余のない繰り返し文字の数で割り切れる必要があります。