统计重复个数
定义str =[s, n]表示 str 由 n 个字符串 s 连接构成。
例如，str == ["abc", 3] =="abcabcabc" 。
如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。
例如，根据定义，s1 = "abc" 可以从 s2 = "abdbec" 获得，仅需要删除加粗且用斜体标识的字符。
现在给你两个字符串s1和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。
请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。
Example:
Input:
s1="acb", n1=4
s2="ab", n2=2
Return:
2
从题目可知，如果s2在str1中出现了N次，那么str2在str1中出现了N/n2次。所以我们只需要算出s2出现的次数就可以算出str2出现的次数。问题转变成str1中s2出现的次数。
如何求出s2出现的次数？一种可行的想法是：对于str1中每一段s1，匹配s1中出现s2的长度，若长度等于s2的长度，那么s2就完整出现过一次，否则下一段s1匹配s2剩余长度。
我们用：
nextchar数组来记录s2中每一位在s1中匹配之后剩余长度在s2中开头的位置reptercount数组来记录s2中当前位是否完整匹配过一次
对于例子：s1="abacb", n1=6，s2="bcaa", n2=1,j表示匹配成功的下标（从0开始）
| j | 1 2 | 3 0 1 | 2 | 3 0 1 | 2 | 3 0 |
|---|---|---|---|---|---|---|
| s1 | abacb | abacb | abacb | abacb | abacb | abacb |
| s2 | bcaa | bcaa | bcaa | bcaa | bcaa | bcaa |
| nextchar | 2 | 1 | 2 | 1 | 2 | 1 |
| repetcount | 0 | 1 | 0 | 1 | 0 | 1 |
处理完成之后，遍历n1次，每次遍历加上当前字符对应的repercount值，并且跳到当前字符对应的nextchar位置
代码实现如下：
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
int s2len = s2.size();
int s1len = s1.size();
vector<int> nextchar(s2len, 0);
vector<int> repetcnt(s2len, 0);
for(int i = 0; i < s2len; i ++)
{
int idx = i;
int cnt = 0;
for(int j = 0; j < s1len; j ++)
{
if(s1[j] == s2[idx])
{
idx ++;
if(idx == s2len)
{
idx = 0;
cnt ++;
}
}
}
nextchar[i] = idx;
repetcnt[i] = cnt;
}
int ans = 0;
int next = 0;
for(int i = 0; i < n1; i ++)
{
ans += repetcnt[next];
next = nextchar[next];
}
return ans / n2;
}
};