C ++中最长的重复子字符串

假设我们有一个字符串S，我们必须找到最长的重复子字符串的长度。如果不存在重复的子字符串，我们将返回0。因此，如果字符串类似于“ abbaba”，则输出将为2。因为最长的重复子字符串为“ ab”或“ ba”。

以字典顺序返回以这种方式可以形成的所有单词。

为了解决这个问题，我们将遵循以下步骤-

• n：= S的大小

• 设置S：=一个与S串联的空格

• 设置ret：= 0

• 创建一个大小为（n + 1）x（n + 1）的矩阵dp

• 对于我在1到n范围内

• 如果S [i] = S [j]

• dp [i，j]：= dp [i，j]和1 + dp [i – 1，j-1]的最大值

• ret：= ret和dp [i，j]的最大值

• 对于范围i +1至n的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