C++で繰り返しを数える

空でない2つの文字列s1とs2（最大100文字）があり、2つの数値n1とn2が両方とも0〜106の範囲にあるとします。ここで、文字列S1とS2を想定します。ここで、S1 =[s1、n1]とS2 =[ s2、n2]。

S =[s、n]は、n個の接続された文字列sで構成される文字列Sを定義します。例として、["ab"、4]="abababab"。

一方、文字列s2から一部の文字を削除してs1になると、文字列s2から文字列s1を取得できることも定義します。したがって、「abc」は定義に基づいて「abdbec」から取得できますが、「acbbe」からは取得できません。

[S2、M]がS1から取得できるように、最大​​の整数Mを見つける必要があります。

したがって、入力がs1 ="acb"、n1 =4、s2 ="ab"、n2 =2の場合、出力は2になります

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

• s2の各文字cについて

  • cがs1にない場合、-

    • 0を返す

• p1：=0、p2：=0、マーク：=0

• p1

  • c：=s2[s2のp2modサイズ]

  • （s1 [s1のp1modサイズ]はcおよびp1

    • （p1を1増やします）

  • （p2を1増やします）

  • （p1を1増やします）

  • s2のp2modサイズが0と同じ場合、-

    • p2がs2のサイズと同じである場合、-

      • マーク：=p1

    • それ以外の場合、s1のp1modサイズがs1のmarkmodサイズと同じである場合、-

      • ラウンド：=（s1のサイズ* n1-p1）/（p1-マーク）

      • p1：=p1 +ラウンド*（p1-マーク）

      • p2：=p2 +ラウンド*（p2-s2のサイズ）

• p2 / s2/n2のサイズを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int getMaxRepetitions(string s1, int n1, string s2, int n2) {
      for (auto c : s2) {
         if (s1.find(c) == string::npos)
            return 0;
      }
      int p1 = 0, p2 = 0, mark = 0;
      while (p1 < s1.length() * n1) {
         char c = s2[p2 % s2.length()];
         while (s1[p1 % s1.length()] != c && p1 <s1.length() * n1)
         p1++;
         p2++;
         p1++;
         if (p2 % s2.length() == 0) {
            if (p2 == s2.length()) {
               mark = p1;
            }
            else if (p1 % s1.length() == mark % s1.length()) {
               int round = (s1.length() * n1 - p1) / (p1 - mark);
               p1 += round * (p1 - mark);
               p2 += round * (p2 - s2.length());
            }
         }
      }
      return p2 / s2.length() / n2;
   }
};
main() {
   Solution ob;
   cout << (ob.getMaxRepetitions("acb",4,"ab",2));
}

入力

"acb",4,"ab",2

出力

2