每日一題打卡：466. 統計重複個數

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/count-the-repetitions

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

題目描述:

由 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 Solution4461 {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        if(n1==0) return 0;
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int l1 = s1.length();
        int l2 = s2.length();
        int couts1=0;//經曆多少s1
        int couts2=0;//經曆多少s2
        int p=0;//目前在s2的位置
        Map<Integer,int[]> mp = new HashMap<>();//記錄每一次s1掃描結束後目前的狀态，尋找循環
        while(couts1<n1){
            for(int i=0;i<l1;i++){
                if(c1[i]==c2[p]){//往前
                    p++;
                    if(p==l2){//s2掃描結束從頭開始循環
                        p=0;
                        couts2++;
                    }
                }
            }
            couts1++;
            if(!mp.containsKey(p)){
                mp.put(p,new int[]{couts1,couts2});//記錄目前狀态

            }
            else{//出現了循環 這次結束後p的位置和以前某一次一樣，就是循環
                int[] last =mp.get(p);
                int circle1= couts1-last[0];
                int circle2= couts2-last[1];
                couts2 += circle2*((n1-couts1)/circle1);
                couts1 += circle1*((n1-couts1)/circle1);//更新新他們
            }
        }
        return couts2/n2;
    }
}