数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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，则可以说字符串 s1 可以从字符串 s2 中得到。“abc”可以从“abdbec”得到，但不能从“acbbe”得到。
我们需要找到最大的整数 M，使得 [S2,M] 可以从 S1 得到。
例如，如果输入为 s1="acb", n1=4, s2="ab", n2=2，则输出为 2
为了解决这个问题，我们将遵循以下步骤：
对于 s2 中的每个字符 c
如果 c 不在 s1 中，则：
返回 0
p1 := 0, p2 := 0, mark := 0
当 p1 < s1 的大小 时，执行：
c := s2[p2 mod s2 的大小]
当 (s1[p1 mod s1 的大小] 不等于 c 且 p1 < s1 的大小 * n1) 时，执行：
(将 p1 加 1)
(将 p2 加 1)
(将 p1 加 1)
如果 p2 mod s2 的大小 等于 0，则：
如果 p2 等于 s2 的大小，则：
mark := p1
否则，当 p1 mod s1 的大小 等于 mark mod s1 的大小 时，则：
round := (s1 的大小 * n1 - p1) / (p1 - mark)
p1 := p1 + round * (p1 - mark)
p2 := p2 + round * (p2 - s2 的大小)
返回 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
249 次浏览
