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