C++で繰り返される部分文字列パターン

空でない文字列があるとします。その部分文字列を取得し、その部分文字列を複数回追加することによって、それを構築できるかどうかを確認する必要があります。文字列は小文字の英字のみで構成され、長さは10000を超えません。したがって、入力が「abaabaaba」の場合、「aba」を使用して作成されるため、答えはtrueになります。

これを解決するには、次の手順に従います-

• 動的計画法のアプローチを使用します。
• サイズnの配列DPを定義します。 nは文字列のサイズです
• i：=1およびj：=0
• while i
• 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