计算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