假设我们有两个非空字符串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