循环节

循环节：指在序列中出现的一种重复的、周期性的模式。这个模式可以是一组连续的元素，也可以是整个序列的重复。

周期性特征：序列中的循环节反映了序列的周期性特征，即序列中的某一段会以某种方式重复出现。

  • 寻找循环节的方法
    • 快慢指针法：用两个指针，一个每次走一步，另一个每次走两步。如果存在循环节，两个指针最终会相遇。
    • 哈希表法：使用哈希表记录每次遍历的状态，如果发现某个状态已经出现过，说明存在循环节。

统计重复个数

定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。

  • 例如，str == ["abc", 3] =="abcabcabc" 。

如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。

  • 例如，根据定义，s1 = "abc" 可以从 s2 = "ab***dbe***c" 获得，仅需要删除加粗且用斜体标识的字符。

现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。

请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。

示例 1：

1
2
输入：s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
输出：2

示例 2：

1
2
输入：s1 = "acb", n1 = 1, s2 = "acb", n2 = 1
输出：1

提示：

  • 1 <= s1.length, s2.length <= 100
  • s1 和 s2 由小写英文字母组成
  • 1 <= n1, n2 <= 10^6

哈希表找循环节

参考官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        // 找循环节
        if (n1 == 0) return 0;
        int s1cnt = 0, s2cnt = 0, idx = 0;
        // recall 是我们用来找循环节的变量，它是一个哈希映射
        // 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果
        Map<Integer, int[]> recall = new HashMap<>();
        int preLoop[], inLoop[];
        while (true) {
            // 遍历s1找循环节
            s1cnt++;
            for (int i = 0; i < s1.length(); i++) {  // 用s1去匹配s2
                if (s1.charAt(i) == s2.charAt(idx)) {
                    idx++;
                    if (idx == s2.length()) {
                        s2cnt++;
                        idx = 0;
                    }
                }
            }
            if (s1cnt == n1) return s2cnt/n2;  // 没有循环节，直接返回当前匹配数量对应的结果
            if (recall.containsKey(idx)) {
                int value[] = recall.get(idx);
                int s1cntPre = value[0], s2cntPre = value[1];
                preLoop = new int[]{s1cntPre, s2cntPre};  // 循环节之前的s1cnt和s2cnt
                inLoop = new int[]{s1cnt - s1cntPre, s2cnt - s2cntPre};  // 循环节的s1cnt和s2cnt
                break;
            }
            else {
                recall.put(idx, new int[]{s1cnt, s2cnt});
            }
        }
        int res = preLoop[1] + (n1 - preLoop[0]) / inLoop[0] * inLoop[1];  // 计算循环节及之前的结果
        int rest = (n1 - preLoop[0]) % inLoop[0];  // 剩下的的s1片段个数
        for (int i = 0; i < rest; i++) {
            for (int j = 0; j < s1.length(); j++) {
                if (s1.charAt(j) == s2.charAt(idx)) {
                    idx++;
                    if (idx == s2.length()) {
                        res++;
                        idx = 0;
                    }
                }
            }
        }
        return res/n2;
    }
}