算法模拟

在模拟过程中找出循环节

字数统计: 3k字   |   阅读时长: 13分
, , , ,

摘要: 循环节优化模拟；倍增优化DP

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在模拟的过程中，如果出现了循环节，就可以直接跳过很多中间的模拟步骤。有时这种循环节是现成已知的，例如文章 通过已知的循环节优化模拟过程 解决的问题。

今天看一个重需要再模拟过程中发现循环节的问题。复子序列的问题，此前我们用倍增优化DP解决了，本文我们通过模拟发现循环节的角度来解决。

$1 题目

466. 统计重复个数

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

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

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

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

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

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

提示：

1
2
3
1 <= s1.length, s2.length <= 100
s1 和 s2 由小写英文字母组成
1 <= n1, n2 <= 1e6

示例 1：
输入：s1 = “acb”, n1 = 4, s2 = “ab”, n2 = 2
输出：2

示例 2：
输入：s1 = “acb”, n1 = 1, s2 = “acb”, n2 = 1
输出：1

$2 题解

算法1: 模拟

有两个字符串 $s_{1}$ 和 $s_{2}$，其中如果想要 $s_{1}$ 删除一些字符后可以得到 $s_{2}$。则 $s_{1}$ 中需要存在子序列 $s_{2}$。

在 $s_{2}$ 可以重复的情况下，只要 $s_{1}$ 中的元素在 $s_{2}$ 中都存在，那么将 $s_{2}$ 重复足够多次后，肯定能出现恰好等于 $s_{2}$ 的子序列。

最坏的情况 $s_{2}$ 每重复一次只能使得子序列多匹配 $s_{1}$ 的 1 个字符，例如：

$s_{1}$ 至少重复 5 次，才能使得其中存在子序列等于 $s_{2}$：

如果 $s_{1}$ 重复的次数更多，那么其中就就有可能存在多个 $s_{2}$ 子序列。其中第 $i$ 个 $s_{2}$ 子序列的开头出现在第 $i - 1$ 个 $s_{2}$ 子序列的后面。

现在考虑 $s_{1}$ 重复的次数比较的情况，重复了 $n_{1}$ 次，记重复后的字符串为 $S_{1}$。现在 $S_{1}$ 中包含的 $s_{2}$ 子序列有 $N$ 个。

若将 $s_{2}$ 重复 $n_{2}$ 次，记为 $S_{2}$。如果 $n_{2}$ 不太大，那么 $S_{1}$ 中仍然有可能出现 $S_{2}$ 子序列甚至多个 $S_{2}$ 子序列，记 $S_{1}$ 中出现的 $S_{2}$ 子序列个数为 $M$。

于是有 $M = \frac{N}{n_{2}}$。

综上，我们可以给出暴力的模拟算法：遍历 $n_{1}$ 次 $s_{1}$, 同时记录 $s_{2}$ 上的一个指针 idx2，当遍历到 $s_{1}$ 的字符与 s2[idx2] 相等的时候，向后推进 idx2，当 $n_{1}$ 次 $s_{1}$ 遍历完了，看 idx2 走了 $s_{2}$ 多少圈，记为 cnt2。

答案为 cnt2 / n2。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int len1 = s1.size(), len2 = s2.size();
        int idx2 = 0, cnt2 = 0; // S1 遍历完一次，s2 循环了多少次

        for(int i = 0; i < n1; ++i)
            for(int idx1 = 0; idx1 < len1; ++idx1)
            {
                if(s1[idx1] == s2[idx2])
                    ++idx2;
                if(idx2 == len2)
                {
                    ++cnt2;
                    idx2 = 0;
                }
            }
        return cnt2 / n2;
    }
};

算法2: 在模拟过程中找循环节

下面我们看一下基于这种循环节的模拟算法，回顾前面的暴力模拟过程：

遍历 $n_{1}$ 次 $s_{1}$, 同时记录 $s_{2}$ 上的一个指针 idx2，当遍历到 $s_{1}$ 的字符与 s2[idx2] 相等的时候，向后推进 idx2，当 $n_{1}$ 次 $s_{1}$ 遍历完了，看 idx2 走了 $s_{2}$ 多少圈，记为 cnt2。

模拟准备

将遍历 $n_{1}$ 次 $s_{1}$ 的过程细化，在 $s_{1}$ 上也记录一个指针 idx1，$s_{1}$ 遍历的圈数记为 cnt1。这样 $(cnt_1, idx_1)$ 代表了 $s_{1}$ 遍历的进度、$(cnt_2, idx_2)$ 代表了 $s_{2}$ 匹配的进度。其中 $0 \leq cnt_1 < n_{1}$、$0 \leq idx_1 < \mathrm{len}(s_{1})$、$0 \leq idx_2 < \mathrm{len}(s_{2})$。

模拟进行

模拟开始时，$(cnt_{1}, idx_{1}) = (0, 0)$, $(cnt_{2}, idx_{2}) = (0, 0)$、当 $s_{2}$ 完成第 $1$ 轮匹配时，$(cnt_2, idx_2) = (1, 0)$。此时记 $(cnt_{1}, idx_{1}) = (c_{1}, i_{1})$。

继续模拟，当 $s_{2}$ 完成第 $2$ 轮匹配时，$(cnt_2, idx_2) = (2, 0)$。此时记 $(cnt_{1}, idx_{1}) = (c_{2}, i_{2})$。

以此类推，当 $s_{2}$ 完成第 $k$ 轮匹配时，$(cnt_2, idx_2) = (k, 0)$。此时记 $(cnt_{1}, idx_{1}) = (c_{k}, i_{k})$。

出现循环

由于 $idx_{1}$ 只能取到 $[0, \mathrm{len}(s_{1}) - 1]$ 的范围，因此当 $k$ 充分大时，总能出现 $i_{k}$ 与前面的某个 $i_{j}, 0\leq j < k$ 相等的情况。当第一次出现这种情况时 $k=K$，$s_{1}$ 遍历和 $s_{2}$ 匹配的状态分别为 $(cnt_{1}, idx_{1}) = (c_{K}, i_{K})$、$(cnt_{2}, idx_{2}) = (K, 0)$。与 $i_{K}$ 相等的是 $i_{J}$，完整的状态为 $(cnt_{1}, idx_{1}) = (c_{J}, i_{J})$、$(cnt_{2}, idx_{2}) = (J, 0)$。

这样我们就在模拟的过程中找到了循环节 $[J, K)$。循环节长度 $L = K - L$，也就是说，从 $(cnt_2, idx_2) = (K, 0)$ 开始，$s_{2}$ 每匹配 $L$ 次，$s_{1}$ 上的遍历状态 $(cnt_{1}, idx_{1})$ 的变化情况都是一样的。$cnt_{1}$ 会增加 $\Delta c = c_{K} - c_{J}$，$idx_{1}$ 仍然保持 $i_{J}$。

跳过循环节

在循环节出现之前，$s_{2}$ 完成了 $K$ 轮匹配，此时 $cnt_{1} = c_{K}$。由于 $cnt_{1} < n_{1}$，因此循环节可以循环的次数 $C$ 满足 $c_{K} + C \times \Delta c \leq n_{1} - 1$。于是 $C = \left\lfloor\frac{n_{1} - 1 - c_{K}}{\Delta c}\right\rfloor$。

$C$ 次循环节走完之后，$s_{1}$ 遍历和 $s_{2}$ 匹配的状态为 $(c_{K} + C\times \Delta c, i_{J})$、$(K + CL, 0)$。

模拟循环节后的残余

此后，$s_{1}$ 还可以再遍历，直至 $(cnt_{1}, idx_{1}) = (n_{1}, 0)$ 时退出，此时 $(cnt_{2}, idx_{2}) = (C_{E}, i_{E})$。

最终 $s_{1}$ 遍历 $n_{1}$ 次，$s_{2}$ 完整匹配了 $C_{E}$ 次。

于是答案 $M = \left\lfloor\frac{C_{E}}{n_{2}}\right\rfloor$。

代码 (C++)

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
class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int len1 = s1.size(), len2 = s2.size();
        int idx1 = 0, cnt1 = 0; // S1 的遍历状态
        int idx2 = 0, cnt2 = 0; // S2 的匹配状态

        unordered_map<int, vector<int>> mapping; // i_k -> k, c_k
        mapping[0] = {0, 0};
        bool flag = false; // 是否已经处理过循环节
        while(cnt1 < n1)
        {
            while(idx1 < len1)
            {
                if(s1[idx1] == s2[idx2])
                    idx2++;
                idx1++;
                if(idx2 == len2)
                {
                    cnt2++;
                    idx2 = 0;
                    if(mapping.count(idx1) == 0)
                    {
                        mapping[idx1] = {cnt2, cnt1};
                    }
                    else if(!flag)
                    {
                        // 发现循环节
                        int K = cnt2;
                        int iK = idx1;
                        int cK = cnt1;
                        int J = mapping[iK][0];
                        int cJ = mapping[iK][1];
                        int L = K - J;
                        int delta_c = cK - cJ;
                        int C = (n1 - cK) / delta_c;
                        cnt1 = cK + C * delta_c;
                        cnt2 = K + C * L;
                    }
                }
            }
            cnt1++;
            idx1 = 0;
        }
        return cnt2 / n2;
    }
};

算法3：另一种循环节

循环节概念可以类比无限循环小数, 例如 3.456789789789… 中 789 为循环节。

因为 s2 中的字母在 s1 出现的顺序是乱的，因此暴力中循环匹配的时候会出现错配：即在上一轮的 s2 还没有匹配完，s1 又开始下一轮遍历了。s1 刚好转完一圈时，s2 匹配到的位置只有 $len(s2)$ 种可能，因此只要 s1 走的圈数够多，s2 上一定会出现循环现象。

我们可以将不断循环的 s2 组成的字符串类比作上面小数部分，去找是否存在一个子串，即循环节，满足不断在 S2 中循环，且这个循环节能对应固定数量的 s1 。

例如: s1: abaacdabc, s2: adcbd，s2 中有的 s1 中也有，因此每过一次 s1，s2 中至少匹配了一个字符。

如下图所示，在第一次出现后，S2 的子串 bdadc 构成一个循环节：之后 bdadc 的每次出现都需要有相应的两段 s1。

这里循环节 “bdadc” 是 s2 的一个旋转。

在模拟中需要观测这种循环，可以维护两个数组：

1
2
next[i] := s1 循环 i 次后，在 s2 遍历到的下标
times[i] := s1 循环 i 次后，在 s2 上循环了几次

循环节判定: i > 0 且 当前 idx2 恰好等于 s1 第 1 次循环完以后的下标 next[0]，此时发现循环节，可以整体计算 cnt2 了(利用循环节优化暴力模拟，暴力模拟也是为了求这个 cnt2)。

代码 (C++)

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
50
// 循环节优化
class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int len1 = s1.size(), len2 = s2.size();
        if(len1 == 0 || len2 == 0 || n1 == 0 || n2 == 0)
            return 0;
        int idx2 = 0, cnt2 = 0; // S1 遍历完一次，s2 循环了多少次
        vector<int> times(n1); // times[i] := s1 循环 i 次后，s2 循环了几次
        vector<int> next(n1); // next[i] := s1 循环 i 次后，s2 下一个匹配的下标

        // 同样是暴力遍历，但是找出循环节就直接退出暴力
        for(int i = 0; i < n1; ++i)
        {
            for(int idx1 = 0; idx1 < len1; ++idx1)
            {
                if(s1[idx1] == s2[idx2])
                    ++idx2;
                if(idx2 == len2)
                {
                    ++cnt2;
                    idx2 = 0;
                }
            }
            times[i] = cnt2;
            next[i] = idx2;
            // 循环节出现：一定 s1 至少遍历完一遍，当前 idx2 与第 1 次遍历完 s1 时相同 (idx2 == next[0])
            if(i > 0 && idx2 == next[0])
            {
                // 第一部分： 交错前
                int head = times[0]; // 交错前的部分
                // 第 2 部分：中间循环部分
                // (n1 - 1)，要减去 1 个，因为从 s1 已经循环了一次开始，才出现的循环节
                // (n1 - 1) / i 表示剩下的部分有多少个红色大括号段（循环节）
                // times[i] - times[0] 表示：每个循环节里出现了几个 s2
                // ((n1 - 1) / i) * (times[i] - times[0]) 就表示中间那部分里面 s2 出现的次数
                int middle = ((n1 - 1) / i) * (times[i] - times[0]);

                // 第 3 部分：交错后
                // (n1 - 1) % i 相对于 (n1 - 1) / i 而言，就是不能整除的部分
                // 减去 times[0] 是因为计算 times[i] 的时候计算的是前缀和，head 这部分已经计算过了，要把它删掉（写成两部分的和也可以）
                int end = times[(n1 - 1) % i] - times[0];

                // 总结：一下子计算出 loopTimesOnS2，是这个解法优化的地方
                return (head + middle + end) / n2;
            }
        }
        return cnt2 / n2;
    }
};

倍增优化DP

s1 第 i 为开始，匹配 $2^{k}$ 个 s2 所需的长度

给定 s1 上的起始点 i，能往前匹配多少个 s2 是确定的，记为 C，因为每个 s2 都是在往右推进无法回头的，因此可以二分 s2 的个数，问匹配这么多个 s2 是否超出 n1 个 s1 的范围了。

因此可以预处理重 dp[i][k] := 起点为 i，匹配 $2^{k}$ 个 s2 所需的长度，终点为 (i + dp[i][k]) % len1。然后用二进制划分的风湿凑出 C。

1
2
dp[i][k] := 起点为 i，匹配 2^k 个 s2 所需的长度
dp[i][k] = dp[i][k - 1] + dp[(i + dp[i][k - 1]) % len1][k - 1]

参考文章：倍增优化DP

代码 (C++)

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
class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        using ll = long long;
        int len1 = s1.size(),len2 = s2.size();
        const int K = 30;
        vector<vector<ll>> dp(len1, vector<ll>(K, 0));
        int l1 = 0,l2 = 0;
        for(int i = 0; i < len1; ++i)
        {
            l1 = i; l2 = 0;
            while(l2<len2)
            {
                while(l1 < n1 * len1 && s1[l1 % len1] != s2[l2])
                    l1++;
                l1++;
                l2++;
            }
            dp[i][0] = l1 - i;
        }
        for(int k = 1; k < K; ++k)
            for(int i = 0; i < len1; ++i)
            {
                dp[i][k] = dp[i][k - 1] + dp[(i + dp[i][k - 1]) % len1][k - 1];
            }
        long long int ans = 0;
        int begin = 0;
        for(int k = 29; k >= 0; k--)
            while((begin + dp[(begin % len1)][k]) <= n1 * len1)
            {
                ans += (1 << k);
                begin += dp[(begin % len1)][k];
            }
        return ans / n2;
    }
};
Share