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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串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

    以上是 C ++中最长的重复子字符串 的全部内容， 来源链接： utcz.com/z/326472.html

    回到顶部