C++で最も長く繰り返される部分文字列

文字列Sがあるとすると、最も長く繰り返される部分文字列の長さを見つける必要があります。繰り返しの部分文字列が存在しない場合は0を返します。したがって、文字列が「abbaba」のような場合、出力は2になります。最も長く繰り返されるサブ文字列は「ab」または「ba」です。

この方法で形成できるすべての単語を辞書式順序で返します。

これを解決するには、次の手順に従います-

• n：=Sのサイズ

• セットS：=Sと連結された1つの空白スペース

• set ret：=0

• サイズ（n + 1）x（n + 1）の1つの行列dpを作成します

• 1からnの範囲のiの場合

  • i+1からnの範囲のjの場合

    • S [i] =S [j]

      の場合

      • dp [i、j]：=dp [i、j]の最大値と1 + dp [i – 1、j-1]

      • ret：=retとdp[i、j]

        の最大値

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestRepeatingSubstring(string S) {
      int n = S.size();
      S = " " + S;
      int ret = 0;
      vector < vector <int> > dp(n + 1, vector <int> (n + 1));
      for(int i = 1; i <= n; i++){
         for(int j = i + 1; j <= n; j++){
            if(S[i] == S[j]){
               dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
               ret = max(ret, dp[i][j]);
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.longestRepeatingSubstring("abbaba"));
}

入力

"abbaba"

出力

2