466.html

<script>
    /**
     *
     *
     定义由 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
     */
    function binarySearch(find, arr, low, high) {
        while (low <= high) {
            let mid = Math.ceil((low + high) / 2);
            if (arr[mid] === find) {
                return mid;
            } else if (arr[mid] < find) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -(low);
    }

    /**
     * @param arr 已从小到大排序的数组
     * @param item
     */
    function insertIfNoRepeat(arr = [], item) {
        let index = binarySearch(item, arr, 0, arr.length);
        if (index < 0) {
            arr.splice(-index, 0, item);
            return -index;
        } else {
            return index;
        }
    }

    var getMaxRepetitions = function (s1, n1, s2, n2) {
        if (n1 === 0) {
            return 0;
        }
        let l1 = s1.length;
        let l2 = s2.length;
        let idx = {};
        let f = [];
        let i = 0;
        let j = 0;
        let L1 = l1 * n1;
        while (i < L1) {
            while (i < L1 && s1[i % l1] !== s2[j % l2]) {
                i++;
            }
            if (i < L1 && (j + 1) % l2 === 0) {
                if (idx[i % l1] === undefined) {
                    idx[i % l1] = f.length;
                    f.push(i);
                } else {
                    let b = idx[i % l1];
                    let a = Object.keys(idx).length;
                    let rest = L1 - f[b];
                    let L = i - f[b];
                    let k = rest % L ? insertIfNoRepeat(f, rest % L + f[b] - 1) : b;
                    let ans = Math.floor(rest / L) * (a - b) + k;
                    console.log(ans, '--', Math.floor(rest / L), '--', a, '--', b, '--', k, '--', n2);
                    return Math.floor(ans / n2);
                }
            }
            i++;
            j++;
        }
        return Math.floor(f.length / n2);
    };
    var getMaxRepetitions1 = function (s1, n1, s2, n2) {
        let c1 = s1.split('');
        let c2 = s2.split('');
        // 标记c2(s2)匹配位置索引
        let index = 0;
        // s1已使用的个数
        let num1 = 0;
        // 匹配单s2成功(不计算乘以n2)的个数
        let num2 = 0;
        while (num1 < n1) {
            for (let i = 0; i < c1.length; i++) {
                if (c1[i] === c2[index]) {
                    if (index === c2.length - 1) {
                        index = 0;
                        num2++;
                    } else {
                        index++;
                    }
                }
            }
            num1++;
        }
        console.log(num2);
        return Math.floor(num2 / n2);
    };
    console.log(getMaxRepetitions("abc", 4, "ab", 2));
    console.log(getMaxRepetitions("acb",
        4,
        "ab",
        2));
</script>