C++で最長の繰り返し部分文字列を求める方法

文字列Sが与えられたとき、その中に含まれる最も長く繰り返される部分文字列の長さを求めることを考えます。繰り返される部分文字列が存在しない場合は0を返します。

例えば、文字列が「abbaba」の場合、出力は2になります。これは、最も長い繰り返し部分文字列が「ab」または「ba」（長さ2）であるためです。

解法のアプローチ：動的計画法（DP）

この問題は、動的計画法を用いて効率的に解くことができます。dp[i][j]を「位置iで終わる部分文字列と位置jで終わる部分文字列の共通接尾辞の長さ」と定義します。文字が一致するたびに、直前の状態に1を加えていくことで、繰り返し部分文字列の長さを段階的に求められます。

具体的には、以下の手順に従います。

• n := 文字列Sのサイズとする
• S := 先頭に空白1文字を連結した文字列とする（インデックスを1始まりにするため）
• ret := 0 で初期化する
• サイズ (n + 1) × (n + 1) の二次元配列 dp を作成する
• i を 1 から n までループする
  • j を i + 1 から n までループする
    • S[i] == S[j] の場合：
      • dp[i][j] := max(dp[i][j], 1 + dp[i - 1][j - 1])
      • ret := max(ret, dp[i][j])
• ret を返す

それでは、以下の実装例を見て理解を深めましょう。

C++での実装例

#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

計算量について

このアルゴリズムの時間計算量はO(n²)、空間計算量もO(n²)です。文字列の長さがnの場合、二重ループですべての文字ペア(i, j)を確認し、各ペアに対して定数時間の処理を行うためです。二次元DPテーブルを使用することで、部分問題の結果を再利用し、重複計算を避けている点がポイントです。