資料結構
網路
關係資料庫管理系統(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+ 次瀏覽
廣告