C ++中的重复子字符串模式

假设我们有一个非空字符串。我们必须检查它是否可以通过获取其子字符串并附加多次子字符串来构造。该字符串仅包含小写英文字母，并且长度不会超过10000。因此，如果输入内容为“ abaabaaba”，则答案将为true，因为它是使用“ aba”创建的

为了解决这个问题，我们将遵循以下步骤-

• 我们将使用动态编程方法。

• 定义大小为n的数组DP。n是字符串的大小

• i：= 1和j：= 0

• 当我<n

• 如果j> 0，则j：= DP [j – 1]

• else dp [i]：= 0，然后将i加1

• 如果str [i] == str [j]，则DP [i]：= j + 1，将i和j加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