统计重复个数--循环结剪枝

0x01.问题

由 n 个连接的字符串 s 组成字符串 S，记作 S = [s,n]。例如，["abc",3]=“abcabcabc”。

如果我们可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。例如，根据定义，“abc” 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。

现在给你两个非空字符串 s1 和 s2（每个最多 100 个字符长）和两个整数 0 ≤ n1 ≤ 10^6 和 1 ≤ n2 ≤ 10^6。现在考虑字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。

请你找出一个可以满足使 [S2,M] 从 S1 获得的最大整数 M 。

示例： 输入： s1 =“acb”,n1 = 4 s2 =“ab”,n2 = 2
返回： 2

public int getMaxRepetitions(String s1, int n1, String s2, int n2) 

0x02.详细分析

初看问题，发现有些晦涩难懂，再读。。。

抓住问题的关键：

• 字符串 S1 由n1个相同的字符串s1构成。
• 字符串 S2 由n2个相同的字符串s2构成。
• 题目要求的是，字符串S2 最多 在S1中出现几次。
• 其中，这个出现指的是只要按照顺序在S1里面出现就行，不需要一定相连。
• 比如：字符串S2='ASCASC'在字符串S1='ADSFCADSFC'最多出现了一次。

弄清楚了问题的本质后，开始想办法去解决这个问题，首先，第一条思路，最原始，最暴力的思路：

• 遍历S1，看在里面最多能找出多少个S2。

这条思路直击问题的本质，毫无疑问是可以解决这个问题的，但是作用并不大。

以为注意到n可能非常的大，所以，如果要遍历完整个的字符串，肯定效率不高。

那么我们就要想办法从中去消减时间，也就是俗称的 剪枝。

如何剪起呢？

我们一刚开始就想生成S1和S2，但是我们似乎忘了点什么，S1和S2都是高度循环的字符串呀，如果我们直接拼起来，那么我们就忽略循环字符串的这个特性，就当做了一个普通的字符串来处理，这也是我们这条思路得弊端。

说明，问题的关键还是要利用这个循环的特性。

我们设想一下，S1是高度循环的，S2也是高度循环的，最终要找的是S2在S1里面出现的次数，如果我们知道在S1里面有这样一个特殊的字符串：

• 它包含了整个的S2，或者S2的一小部分相同的字符串，并且，它在S1里面循环出现。

如果有这样一个字符串，那么，我们后面的计算，只要做简单的乘法运算，即可算出中间一大段的数量，这样省去了非常多的时间。

然后，问题就来到了如何去寻找这样的字符串，（这样的字符串其实叫做循环结）

• 我们可以维护一个哈希表，索引是s2里面的一个下标，代表当前匹配到s2里面的index位，而此时匹配的状态，记录当前匹配到第cous1个s1，第cous2个s2。
• 如果相同的下标在哈希表内重复出现了，说明找到了一个循环结。
• 说明：说明再两次匹配中，匹配到相同的s2，所以出现了循环结。

找到循环结后，计算出中间一大段的cous1和cous2，最后整理答案：

• 模拟cir1表示，这个循环结占据多少个s1。
• 模拟cir2表示，这个循环结占据多少个s2。
• 那么匹配s1的个数cous1+=cir1*((n1-cous1)/cir1)
• 那么匹配s2的个数cous2+=cir2*((n1-cous1)/cir1)
• 最终返回的是cous2/n2，表示总共匹配的s2的个数与S2里面s2的个数之比。

0x03.解决代码–循环结剪枝

class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) 
    {
        if(n1==0||n2==0) return 0;
        char[] c1=s1.toCharArray();
        char[] c2=s2.toCharArray();
        int len1=s1.length();
        int len2=s2.length();
        int cous1=0;//记录遍历s1的次数
        int cous2=0;//记录遍历s2的次数
        int index=0;//记录遍历s2的下标
        //哈希表记录每一次遍历s1后，对于index而言此时匹配的状态值
        Map<Integer,int[]> hash=new HashMap<>();
        while(cous1<n1){
            //遍历s1
            for(int i=0;i<len1;i++){
                //匹配s2中的字符
                if(c1[i]==c2[index]){
                    index++;
                    //匹配到s2的末尾
                    if(index==len2){
                        index=0;
                        cous2++;
                    }
                }
            }
            cous1++;
            
            if(!hash.containsKey(index)){
                //未出现相同状态，直接存入哈希表
                hash.put(index,new int[]{cous1,cous2});
            }else{
                //出现相同状态，说明出现了循环结
                int[] cou=hash.get(index);
                //这个循环结在s1里面占多少个相同字段数
                int cir1=cous1-cou[0];
                //这个循环结在s2里面占多少个相同字段数
                int cir2=cous2-cou[1];
                // s2中占的相同字段数  *  剩下循环的次数        
                cous2+=cir2*((n1-cous1)/cir1);
                // s1中占的相同字段数  *  剩下循环的次数
                cous1+=cir1*((n1-cous1)/cir1);
            }
        }
        //最终的答案是匹配的s2的总次数/s2的总重复数
        return cous2/n2;
    }
}

ATFWUS --Writing By 2020–04-19