Mẫu chuỗi con lặp lại trong C ++

Giả sử chúng ta có một chuỗi không rỗng. Chúng ta phải kiểm tra xem nó có thể được xây dựng hay không bằng cách lấy một chuỗi con của nó và nối nhiều lần chuỗi con. Chuỗi chỉ bao gồm các chữ cái tiếng Anh viết thường và độ dài của nó sẽ không vượt quá 10000. Vì vậy, nếu đầu vào là “abaabaaba”, thì câu trả lời sẽ là true, vì điều này được tạo bằng cách sử dụng “aba”

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Chúng tôi sẽ sử dụng phương pháp lập trình động.
• Xác định một DP mảng có kích thước n. n là kích thước của chuỗi
• i:=1 và j:=0
• trong khi tôi
• nếu str [i] ==str [j], thì DP [i]:=j + 1, tăng i và j lên 1
• nếu không thì
  • nếu j> 0, thì j:=DP [j - 1]
  • else dp [i]:=0 và tăng i lên 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

"abaabaaba"

Đầu ra

true