计算C ++中的重复次数

假设我们有两个非空字符串s1和s2(最多100个字符),两个数字n1和n2都在0到106的范围内。现在假设字符串S1和S2,其中S1 = [s1,n1]和S2 = [ s2,n2]。

S = [s,n]定义字符串S,它由n个相连的字符串s组成。举个例子,[“ ab”,4] =“ abababab”。

另一方面,我们还定义,如果我们从s2中删除一些字符,使其成为s1,则可以从字符串s2获得字符串s1。因此,可以根据定义从“ abdbec”获得“ abc”,但不能从“ acbbe”获得。

我们必须找到最大整数M,以便可以从S1获得[S2,M]。

因此,如果输入像s1 =“ acb”,n1 = 4,s2 =“ ab”,n2 = 2,那么输出将为2

为了解决这个问题,我们将遵循以下步骤-

  • 对于s2中的每个字符c

    • 返回0

    • 如果c不在s1中,则-

    • p1:= 0,p2:= 0,标记:= 0

    • 当p1 <s1的大小时,-

      • 如果p2与s2的大小相同,则-

      • 否则,如果s1的p1 mod大小与s1的标记mod大小相同,则-

      • 标记:= p1

      • 圆形:=(s1的大小* n1-p1)/(p1-标记)

      • p1:= p1 +舍入*(p1-标记)

      • p2:= p2 +舍入*(p2-s2的大小)

      • (将p1加1)

      • c:= s2 [s2的p2 mod大小]

      • 而(s1 [s1的p1 mod大小]不等于c且p1 <s1的大小* n1),则-

      • (将p2增大1)

      • (将p1加1)

      • 如果s2的p2 mod大小等于0,则-

      • 返回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