数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学C++中最长重复子串
假设我们有一个字符串 S，我们需要找到最长重复子串的长度。如果不存在重复子串，则返回 0。例如，如果字符串是“abbaba”，则输出为 2，因为最长的重复子串是“ab”或“ba”。
按字典序返回所有可以这样形成的单词。
为了解决这个问题，我们将遵循以下步骤：
n := S 的大小
设置 S := 一个空格与 S 连接
设置 ret := 0
创建一个大小为 (n + 1) x (n + 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
更新于：2020年4月30日
2K+ 次浏览
广告