数据结构
网络
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+ 浏览量
广告