leetcode 466. 统计重复个数(成功率0.1‱)

由 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-the-repetitions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路分析

这道题，作为每日一题，很难！
想了十几分钟，就看官方解答去了，别笑我啊，实在想不出来这样子弄。
根据题目所给的条件，s1,s2都是循环的字串，那么s2在s1中存在的话，那么是否这个存在的数目与循环有关，或者说，与循环的节点有关？答案是显然的，因为除了能够在s1内部完全找到s2的这种概率蛮小的情形外，大多数应该都是连接的s1构造出来的s2。

1. 那么根据以上分析，我们可以在s1中找到s2在s1中出现的规律即可。
2. 附上官方解图(链接：leetcode 统计重复个数)
   
   那么代码就可产出了。

---

代码分析

仿照Leetcode官方所给解述写出以下代码

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int s1_num = 0,s2_num = 0,index = 0;
        map<int,pair<int,int>> match;
        pair<int, int> Base_str, Loop_str;

        while(true){//寻找循环节
            ++s1_num;
            for(auto it:s1){
                if(it == s2[index]){
                    ++index;
                    if(index == s2.size()){
                        index = 0;
                        ++s2_num;
                    }
                }
            }
            if(s1_num == n1)//将是遍历完也未找到
                return s2_num / n2;
            if(match.count(index)){//已经存在该值即前面应出现过一次时
                pair<int,int> temp = match[index];
                Base_str = {temp.first, temp.second};//记录第一次出现时的值
                Loop_str = {s1_num - temp.first, s2_num - temp.second};//重复出现一次的间隔
                break;
            }
            else 
                match[index] = {s1_num, s2_num};//未出现重复时，入堆
        }

        //计算循环节出现的个数
        int result = Base_str.second + (n1 - Base_str.first) / Loop_str.first * Loop_str.second;

        //计算除循环节外的字串个数
        for(int i = 1;i <= (n1 - Base_str.first) % Loop_str.first;++i){
            for(auto it:s1){
                if(it == s2[index]){
                    ++index;
                    if(index == s2.size()){//匹配一次
                        index = 0;
                        ++result;
                    }
                }
            }
        }
        //由于以上计算的是单个说字串个数，那么S2是由n2个字串组成，那么结果还要除以n2
        return result / n2;
    }
};