3112、访问消失节点的最小时间

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

链接：https://leetcode-cn.com/problems/count-the-repetitions

题解

1、暴力遍历统计

• 代码

// java
class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        /**
         * index为c2的索引， num1当前使用了ss1的个数， num2当前匹配的ss2的个数
         */
        int index = 0 , num1 = 0, num2 = 0;
        while(num1 < n1){
            for(int i = 0 ; i < c1.length ; i++){
                if(c1[i] == c2[index]){
                    if(index == c2.length - 1) {
                        index = 0;
                        num2 ++;
                    }else{
                        index ++;
                    }      
                }
            }
            num1++;
        }
        return num2 / n2;
    }
}

// 作者：liu-jia-liang
// 链接：https://leetcode-cn.com/problems/count-the-repetitions/solution/javajie-fa-by-liu-jia-liang-9/

2、找S2在S1中的循环节

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        if (n1 == 0)
            return 0;
        int[] indexr = new int[s2.length() + 1]; // index at start of each s1 block
        int[] countr = new int[s2.length() + 1]; // count of repititions till the present s1 block
        int index = 0, count = 0;
        for (int i = 0; i < n1; i++) {
            // 遍历一遍字符串s1
            for (int j = 0; j < s1.length(); j++) {
                if (s1.charAt(j) == s2.charAt(index))
                    ++index;
                if (index == s2.length()) {
                    index = 0;
                    ++count;
                }
            }
            countr[i] = count;
            indexr[i] = index;
            for (int k = 0; k < i; k++) {
                // 找到循环节
                if (indexr[k] == index) {
                    // 公式计算
                    int prev_count = countr[k];
                    int pattern_count = (countr[i] - countr[k]) * ((n1 - 1 - k) / (i - k));
                    int remain_count = countr[k + (n1 - 1 - k) % (i - k)] - countr[k];
                    // 返回结果
                    return (prev_count + pattern_count + remain_count) / n2;
                }
            }
        }
        // 没有找到循环节
        return countr[n1 - 1] / n2;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com