資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究C++ 中的重複子字串模式
假設我們有一個非空字串。我們必須檢查它是否可以透過取它的一個子字串並多次新增該子字串來構建。該字串僅包含小寫英語字母，其長度不會超過 10000。因此，如果輸入類似於“abaabaaba”，那麼答案將為真，因為這是使用“aba”建立的
要解決這個問題，我們將遵循以下步驟 −
- 我們將使用動態規劃方法。
- 定義大小為 n 的陣列 DP。n 是字串的大小
- i := 1，j := 0
- while i < n
- 如果 str[i] == str[j]，則 DP[i] := j + 1，將 i 和 j 遞增 1
- 否則
- 如果 j > 0，則 j := DP[j – 1]
- 否則，dp[i] := 0，並將 i 遞增 1
- 如果 DP[n – 1] 不為 0 且 n % (n – DP[n – 1]) == 0
- 返回真
- 否則返回假
示例
讓我們看看以下實現，以獲得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void printVector(vector <int> v){
for(int i = 0; i < v.size(); i++)cout << v[i] << " ";
cout << endl;
}
bool repeatedSubstringPattern(string s) {
int n = s.size();
vector <int> dp(n);
int i = 1;
int j = 0;
while(i < n){
if(s[i] == s[j]){
dp[i] = j+1;
i++;
j++;
} else {
if(j > 0){
j = dp[j-1];
} else {
dp[i] = 0;
i++;
}
}
}
return dp[n - 1] && n % (n - dp[n-1]) == 0;
}
};
main(){
Solution ob;
string res = (ob.repeatedSubstringPattern("abaabaaba"))? "true" : "fasle";
cout << res;
}輸入
"abaabaaba"
輸出
true
更新於：28-Apr-2020
1K+ 瀏覽量
廣告