비어 있지 않은 문자열이 있다고 가정합니다. 부분 문자열을 가져와서 부분 문자열을 여러 번 추가하여 구성할 수 있는지 여부를 확인해야 합니다. 문자열은 영문 소문자로만 구성되며 길이는 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