|
定义由 n 个连接的字符串 s 组成字符串 S，即 S = [s,n]。例如，["abc", 3]=“abcabcabc”。
另一方面，如果我们可以从 s2 中删除某些字符使其变为 s1，我们称字符串 s1 可以从字符串 s2 获得。例如，“abc” 可以根据我们的定义从 “abdbec” 获得，但不能从 “acbbe” 获得。
现在给出两个非空字符串 S1 和 S2（每个最多 100 个字符长）和两个整数 0 ≤ N1 ≤ 106 和 1 ≤ N2 ≤ 106。现在考虑字符串 S1 和 S2，其中S1=[s1,n1]和S2=[s2,n2]。找出可以使[S2,M]从 S1 获得的最大整数 M。
示例：
输入：
s1 ="acb",n1 = 4
s2 ="ab",n2 = 2
返回：
2
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
vector<int> repeatCnt(n1 + 1, 0);
vector<int> nextIdx(n1 + 1, 0);
int j = 0, cnt = 0;
for (int k = 1; k <= n1; ++k) {
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] == s2[j]) {
++j;
if (j == s2.size()) {
j = 0;
++cnt;
}
}
}
repeatCnt[k] = cnt;
nextIdx[k] = j;
for (int start = 0; start < k; ++start) {
if (nextIdx[start] == j) {
int interval = k - start;
int repeat = (n1 - start) / interval;
int patternCnt = (repeatCnt[k] - repeatCnt[start]) * repeat;
int remainCnt = repeatCnt[start + (n1 - start) % interval];
return (patternCnt + remainCnt) / n2;
}
}
}
return repeatCnt[n1] / n2;
}
}; | 
转播
