C++의 반복되는 부분 문자열 패턴

비어 있지 않은 문자열이 있다고 가정합니다. 부분 문자열을 가져와서 부분 문자열을 여러 번 추가하여 구성할 수 있는지 여부를 확인해야 합니다. 문자열은 영문 소문자로만 구성되며 길이는 10000을 초과하지 않습니다. 따라서 입력이 "abaabaaba"와 같으면 "aba"를 사용하여 생성되므로 응답은 true가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 동적 프로그래밍 방식을 사용할 것입니다.
• 크기가 n인 어레이 DP를 정의합니다. n은 문자열의 크기입니다.
• i :=1 및 j :=0
• 내가 인 동안
• str[i] ==str[j]이면 DP[i] :=j + 1, i와 j를 1만큼 증가
• 그렇지 않으면
  • j> 0이면 j :=DP[j – 1]
  • else dp[i] :=0, i를 1 증가

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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