计算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的p1mod大小与s1的标记mod大小相同，则-
标记：=p1
圆形：=（s1的大小*n1-p1）/（p1-标记）
p1：=p1+舍入*（p1-标记）
p2：=p2+舍入*（p2-s2的大小）
（将p1加1）
c：=s2[s2的p2mod大小]
而（s1[s1的p1mod大小]不等于c且p1<s1的大小*n1），则-
（将p2增大1）
（将p1加1）
如果s2的p2mod大小等于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