466. 统计重复个数

定义由 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 Solution {

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

        if(s1 == null || s2 == null) return 0;

        int n = s1.length(), m = s2.length();

        int index = 0, cnt = 0;

        int[] count = new int[m+2], nxt = new int[m+2];

        for(int i = 1; i <= m + 1 && i <= n1; ++i){

            for(int j = 0; j < n; ++j){

                if(s2.charAt(index) == s1.charAt(j)) index++;

                if(index >= m){

                    index = 0;

                    cnt++;

                }

            }

            count[i] = cnt;

            nxt[i] = index;

            for(int j = 1; j < i; ++j){

                if(nxt[j] == nxt[i]){

                    int repeat = count[i] - count[j];

                    int repeat_num = repeat * ((n1 - j) / (i - j));

                    int remain_num = count[j + (n1 - j) % (i - j)];

                    return (repeat_num + remain_num) / n2;

                }

            }

        }

        return count[n1] / n2;

    }

}