线性动态规划：统计重复个数（Count The Repetitions）
字数 4231 2025-12-20 02:37:17

线性动态规划：统计重复个数（Count The Repetitions）

题目描述

定义字符串 s1 的 n1 次重复为：将 s1 重复连接 n1 次得到的新字符串。类似地，s2 的 n2 次重复是将 s2 重复连接 n2 次。

现在给定两个非空字符串 s1、s2 和两个整数 n1、n2。我们需要找出最大的整数 M，使得从 s1 的 n1 次重复构成的字符串中，可以删除一些字符（不能改变剩余字符的相对顺序），从而得到 s2 的 M 次重复构成的字符串。

换句话说，S1 = [s1, n1] 表示由 n1 个 s1 连接而成的字符串，S2 = [s2, n2] 表示由 n2 个 s2 连接而成的字符串。求最大的非负整数 M，使得 S2 是 S1 的子序列。

示例：

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

解释：
S1 = "acbacbacbacb"
S2 = "abab"

从 S1 中可以选出子序列 "a_b_a_b"（下划线表示未选取的字符），即 S2。
所以 M = 1（因为 S2 是 [s2, n2=2]，而得到的子序列对应的是 [s2, M=1]，即 "ab"）。
实际上，我们要求的是最大的 M，使得 [s2, M] 是 S1 的子序列。
但题目中给定的 n2 是用于定义 S2 的，我们需要输出的是 M / n2 的整数部分，即 floor(M / n2)。
但更常见的理解是：S2 由 n2 个 s2 组成，我们想从 S1 中找出最多的完整 s2 重复，即求最大的 M 使得 [s2, M] 是 S1 的子序列，然后返回 floor(M / n2)。

在示例中：
若 M = 2，则 [s2, 2] = "abab"，它是 S1 的子序列吗？从 S1 中选取 "a_b_a_b" 是可行的，所以 M=2。
但题目最终输出的是 M / n2 = 2 / 2 = 1。

题目通常表述为：
给定 s1, n1, s2, n2，求最大的整数 M，使得 [s2, M] 是 [s1, n1] 的子序列，然后返回 floor(M / n2)。

实际上，LeetCode 上的“统计重复个数”问题（LeetCode 466）就是这样的定义。我们要求的就是这个 floor(M / n2) 的值。

解题思路

第一步：理解问题本质

我们有一个很长的字符串 S1，它由 n1 个 s1 拼接而成。我们想从中按顺序选取字符，拼出尽可能多个 s2 的重复（即 [s2, M]）。问最多能拼出多少个完整的 s2？答案就是 floor(M / n2)。

例如，如果最多能拼出 7 个 s2，且 n2 = 2，那么 floor(7 / 2) = 3，表示能组成 3 个完整的 S2（因为每个 S2 由 2 个 s2 组成）。

第二步：暴力模拟的不可行性

最直接的想法：模拟从 S1 中逐个字符匹配 s2 的重复。但 n1 可能非常大（达到 10^6），s1 和 s2 长度不超过 100，所以 S1 的长度可能达到 10^8，不能直接构造出 S1 再进行匹配。

我们需要寻找一种高效的方法，利用 s1 和 s2 是重复的这一周期性特点。

第三步：状态定义与循环检测

考虑这样一个过程：
我们有一个指针 i 遍历 S1 的字符（但不实际构造 S1，而是循环使用 s1），同时我们尝试匹配 s2 中的字符。

定义：

  • 我们用 count 表示到目前为止，已经成功匹配了多少个完整的 s2。
  • 我们用 j 表示当前正在匹配 s2 中的第几个字符（索引从 0 开始）。

关键观察：
由于 s1 是重复的，当我们匹配完若干个 s1 后，j 的值可能会回到之前某个状态。如果我们在第 k 个 s1 的开头时，j 的值与之前第 p 个 s1 开头时的 j 相同，那么从第 p 个 s1 到第 k 个 s1 这段过程会形成一个循环。在这个循环中，每消耗一定数量的 s1，就会匹配出一定数量的 s2。

第四步：动态规划预处理

设 len1 = s1.length(), len2 = s2.length()。
我们定义 dp[i] 表示：从 s2 的第 i 个字符（0-indexed）开始匹配，当遍历完一个完整的 s1 后，能匹配到 s2 的哪个位置，以及在这个过程中匹配了多少个完整的 s2。

更具体地：
我们对于每个 i（0 <= i < len2），模拟从 s2[i] 开始，遍历 s1 的每一个字符：

  • 如果当前 s1 的字符等于 s2[j]（j 是当前 s2 的指针），则 j 前进 1。
  • 如果 j 达到 len2，说明匹配完一个完整的 s2，则计数加 1，并将 j 重置为 0。
    遍历完 s1 的所有字符后，我们记录：
    dp[i] = (nextJ, countDelta)，其中 nextJ 是下一个 s1 开始时 s2 的指针位置，countDelta 是在这个 s1 中匹配到的完整 s2 的数量。

第五步：利用循环加速

现在我们从 j = 0 开始，用 n1 个 s1 进行匹配。
我们维护两个数组：

  • nextIndex[pos]：记录当处理到第 k 个 s1 时，起始的 j 值。
  • count[pos]：记录到第 k 个 s1 结束时，累计匹配到的完整 s2 的数量。

我们从第一个 s1 开始，每次利用 dp[j] 跳到下一个 j 并增加匹配数。同时，我们检查当前起始的 j 是否在之前出现过（即是否出现了循环）。如果出现过，说明从那个位置到当前位置是一个循环节。

假设循环节从第 start 个 s1 开始，到第 i 个 s1 结束（但不包括第 i 个），即 start 和 i 的起始 j 相同。那么：

  • 循环节的长度（以 s1 的个数计）为 cycleLen = i - start。
  • 在每个循环节中，匹配到的 s2 数量为 cycleCount = count[i] - count[start]。

那么剩下的 n1 - i 个 s1 中，我们可以快速计算：还有 remain = n1 - i 个 s1，可以组成 fullCycles = remain / cycleLen 个完整循环，每个循环增加 cycleCount 个 s2。然后剩下 remain % cycleLen 个 s1，我们可以通过查表快速得到它们增加的 s2 数量。

第六步：算法步骤

  1. 预处理 dp[i] 数组。
  2. 初始化 j = 0, totalCount = 0。
  3. 用数组 position 记录每个 j 值第一次出现在第几个 s1 的开始（初始化为 -1 表示未出现）。
  4. 遍历 k 从 0 到 n1-1：
    • 如果 position[j] 不为 -1，说明遇到了循环，进入快速计算阶段。
    • 否则记录 position[j] = k，并记录 countAtStart[k] = totalCount。
    • 然后应用 dp[j]：totalCount += dp[j].countDelta，j = dp[j].nextJ。
  5. 如果遇到循环（假设循环开始于第 start 个 s1，当前是第 i 个 s1 的开始）：
    • cycleLen = i - start
    • cycleCount = totalCount - countAtStart[start]
    • remain = n1 - i
    • totalCount += cycleCount * (remain / cycleLen)
    • 然后处理剩余 remain % cycleLen 个 s1：通过查表快速加上这些 s1 带来的 s2 数量（可以利用 dp 和 countAtStart 的差值计算）。
  6. 最终 totalCount 就是最多能匹配出的完整 s2 的数量 M。
  7. 答案就是 totalCount / n2（整数除法）。

第七步：举例说明

以 LeetCode 466 的示例：

s1 = "acb", n1 = 4
s2 = "ab", n2 = 2

  1. 预处理 dp：

    • i=0（从 s2[0]='a' 开始）：
      遍历 s1："a" 匹配 a，j=1；"c" 不匹配 b；"b" 匹配 b，j=2（等于 len2），计数加 1，j 重置为 0。所以 dp[0] = (0, 1)。
    • i=1（从 s2[1]='b' 开始）：
      遍历 s1："a" 不匹配 b；"c" 不匹配 b；"b" 匹配 b，j=2，计数加 1，重置为 0。所以 dp[1] = (0, 1)。
      实际上 dp[0] 和 dp[1] 相同。

  2. 模拟匹配：

    • 初始 j=0, totalCount=0。
    • 第 0 个 s1 开始：position[0]=0, countAtStart[0]=0。
      应用 dp[0]: totalCount=1, j=0。
    • 第 1 个 s1 开始：j=0 已出现，循环检测：start=0, i=1。
      cycleLen=1, cycleCount=1-0=1, remain=4-1=3。
      totalCount += 1 * (3 / 1) = 3，所以 totalCount=1+3=4。
      剩余 remain % cycleLen = 0，无需额外处理。
    • 结束。totalCount=4，表示能匹配出 4 个完整的 s2（即 "ab"）。
      但 S2 由 2 个 s2 组成，所以能组成 4 / 2 = 2 个完整的 S2。
      然而题目输出的是 floor(M / n2)，其中 M 是匹配的 s2 个数，这里 M=4, n2=2，输出为 2。

注意：LeetCode 466 的示例输出是 2，与我们计算一致。

第八步：边界情况

  • 如果 s2 中某个字符在 s1 中不存在，则直接返回 0。
  • 如果 n1 很小，可能没遇到循环就结束了，所以需要处理非循环的情况。
  • 注意 totalCount 可能很大，需要用 long long 存储。

总结

本题的关键在于发现重复 s1 匹配 s2 时的状态循环，并用动态规划预处理每个状态下遍历一个 s1 后的转移结果。通过检测循环，我们可以在 O(len1 * len2) 的预处理后，用 O(len2) 的额外空间和 O(n1) 的时间（但通过循环跳跃实际更快）计算出最多匹配的 s2 数量，从而得到答案。

这种方法避免了直接模拟超长字符串，高效利用了周期性，是线性动态规划中结合状态机与循环检测的经典题目。

线性动态规划：统计重复个数（Count The Repetitions） 题目描述 定义字符串 s1 的 n1 次重复为：将 s1 重复连接 n1 次得到的新字符串。类似地， s2 的 n2 次重复是将 s2 重复连接 n2 次。 现在给定两个非空字符串 s1 、 s2 和两个整数 n1 、 n2 。我们需要找出最大的整数 M ，使得从 s1 的 n1 次重复构成的字符串中，可以删除一些字符（不能改变剩余字符的相对顺序），从而得到 s2 的 M 次重复构成的字符串。 换句话说， S1 = [s1, n1] 表示由 n1 个 s1 连接而成的字符串， S2 = [s2, n2] 表示由 n2 个 s2 连接而成的字符串。求最大的非负整数 M ，使得 S2 是 S1 的子序列。 示例： 题目通常表述为： 给定 s1, n1, s2, n2，求最大的整数 M，使得 [ s2, M] 是 [ s1, n1 ] 的子序列，然后返回 floor(M / n2)。 实际上，LeetCode 上的“统计重复个数”问题（LeetCode 466）就是这样的定义。我们要求的就是这个 floor(M / n2) 的值。 解题思路 第一步：理解问题本质 我们有一个很长的字符串 S1 ，它由 n1 个 s1 拼接而成。我们想从中按顺序选取字符，拼出尽可能多个 s2 的重复（即 [s2, M] ）。问最多能拼出多少个完整的 s2 ？答案就是 floor(M / n2) 。 例如，如果最多能拼出 7 个 s2 ，且 n2 = 2 ，那么 floor(7 / 2) = 3 ，表示能组成 3 个完整的 S2 （因为每个 S2 由 2 个 s2 组成）。 第二步：暴力模拟的不可行性 最直接的想法：模拟从 S1 中逐个字符匹配 s2 的重复。但 n1 可能非常大（达到 10^6）， s1 和 s2 长度不超过 100，所以 S1 的长度可能达到 10^8，不能直接构造出 S1 再进行匹配。 我们需要寻找一种高效的方法，利用 s1 和 s2 是重复的这一周期性特点。 第三步：状态定义与循环检测 考虑这样一个过程： 我们有一个指针 i 遍历 S1 的字符（但不实际构造 S1 ，而是循环使用 s1 ），同时我们尝试匹配 s2 中的字符。 定义： 我们用 count 表示到目前为止，已经成功匹配了多少个完整的 s2 。 我们用 j 表示当前正在匹配 s2 中的第几个字符（索引从 0 开始）。 关键观察 ： 由于 s1 是重复的，当我们匹配完若干个 s1 后， j 的值可能会回到之前某个状态。如果我们在第 k 个 s1 的开头时， j 的值与之前第 p 个 s1 开头时的 j 相同，那么从第 p 个 s1 到第 k 个 s1 这段过程会形成一个循环。在这个循环中，每消耗一定数量的 s1 ，就会匹配出一定数量的 s2 。 第四步：动态规划预处理 设 len1 = s1.length() , len2 = s2.length() 。 我们定义 dp[i] 表示：从 s2 的第 i 个字符（0-indexed）开始匹配，当遍历完一个完整的 s1 后，能匹配到 s2 的哪个位置，以及在这个过程中匹配了多少个完整的 s2 。 更具体地： 我们对于每个 i （0 <= i < len2），模拟从 s2[i] 开始，遍历 s1 的每一个字符： 如果当前 s1 的字符等于 s2[j] （ j 是当前 s2 的指针），则 j 前进 1。 如果 j 达到 len2 ，说明匹配完一个完整的 s2 ，则计数加 1，并将 j 重置为 0。 遍历完 s1 的所有字符后，我们记录： dp[i] = (nextJ, countDelta) ，其中 nextJ 是下一个 s1 开始时 s2 的指针位置， countDelta 是在这个 s1 中匹配到的完整 s2 的数量。 第五步：利用循环加速 现在我们从 j = 0 开始，用 n1 个 s1 进行匹配。 我们维护两个数组： nextIndex[pos] ：记录当处理到第 k 个 s1 时，起始的 j 值。 count[pos] ：记录到第 k 个 s1 结束时，累计匹配到的完整 s2 的数量。 我们从第一个 s1 开始，每次利用 dp[j] 跳到下一个 j 并增加匹配数。同时，我们检查当前起始的 j 是否在之前出现过（即是否出现了循环）。如果出现过，说明从那个位置到当前位置是一个循环节。 假设循环节从第 start 个 s1 开始，到第 i 个 s1 结束（但不包括第 i 个），即 start 和 i 的起始 j 相同。那么： 循环节的长度（以 s1 的个数计）为 cycleLen = i - start 。 在每个循环节中，匹配到的 s2 数量为 cycleCount = count[i] - count[start] 。 那么剩下的 n1 - i 个 s1 中，我们可以快速计算：还有 remain = n1 - i 个 s1 ，可以组成 fullCycles = remain / cycleLen 个完整循环，每个循环增加 cycleCount 个 s2 。然后剩下 remain % cycleLen 个 s1 ，我们可以通过查表快速得到它们增加的 s2 数量。 第六步：算法步骤 预处理 dp[i] 数组。 初始化 j = 0 , totalCount = 0 。 用数组 position 记录每个 j 值第一次出现在第几个 s1 的开始（初始化为 -1 表示未出现）。 遍历 k 从 0 到 n1-1 ： 如果 position[j] 不为 -1，说明遇到了循环，进入快速计算阶段。 否则记录 position[j] = k ，并记录 countAtStart[k] = totalCount 。 然后应用 dp[j] ： totalCount += dp[j].countDelta ， j = dp[j].nextJ 。 如果遇到循环（假设循环开始于第 start 个 s1 ，当前是第 i 个 s1 的开始）： cycleLen = i - start cycleCount = totalCount - countAtStart[start] remain = n1 - i totalCount += cycleCount * (remain / cycleLen) 然后处理剩余 remain % cycleLen 个 s1 ：通过查表快速加上这些 s1 带来的 s2 数量（可以利用 dp 和 countAtStart 的差值计算）。 最终 totalCount 就是最多能匹配出的完整 s2 的数量 M 。 答案就是 totalCount / n2 （整数除法）。 第七步：举例说明 以 LeetCode 466 的示例： 预处理 dp ： i=0 （从 s2[0]='a' 开始）： 遍历 s1 ："a" 匹配 a ， j=1 ；"c" 不匹配 b ；"b" 匹配 b ， j=2 （等于 len2），计数加 1， j 重置为 0。所以 dp[0] = (0, 1) 。 i=1 （从 s2[1]='b' 开始）： 遍历 s1 ："a" 不匹配 b ；"c" 不匹配 b ；"b" 匹配 b ， j=2 ，计数加 1，重置为 0。所以 dp[1] = (0, 1) 。 实际上 dp[0] 和 dp[1] 相同。 模拟匹配： 初始 j=0 , totalCount=0 。 第 0 个 s1 开始： position[0]=0 , countAtStart[0]=0 。 应用 dp[0] : totalCount=1 , j=0 。 第 1 个 s1 开始： j=0 已出现，循环检测： start=0 , i=1 。 cycleLen=1 , cycleCount=1-0=1 , remain=4-1=3 。 totalCount += 1 * (3 / 1) = 3 ，所以 totalCount=1+3=4 。 剩余 remain % cycleLen = 0 ，无需额外处理。 结束。 totalCount=4 ，表示能匹配出 4 个完整的 s2 （即 "ab"）。 但 S2 由 2 个 s2 组成，所以能组成 4 / 2 = 2 个完整的 S2 。 然而题目输出的是 floor(M / n2) ，其中 M 是匹配的 s2 个数，这里 M=4 , n2=2 ，输出为 2 。 注意：LeetCode 466 的示例输出是 2 ，与我们计算一致。 第八步：边界情况 如果 s2 中某个字符在 s1 中不存在，则直接返回 0。 如果 n1 很小，可能没遇到循环就结束了，所以需要处理非循环的情况。 注意 totalCount 可能很大，需要用 long long 存储。 总结 本题的关键在于发现重复 s1 匹配 s2 时的状态循环，并用动态规划预处理每个状态下遍历一个 s1 后的转移结果。通过检测循环，我们可以在 O(len1 * len2) 的预处理后，用 O(len2) 的额外空间和 O(n1) 的时间（但通过循环跳跃实际更快）计算出最多匹配的 s2 数量，从而得到答案。 这种方法避免了直接模拟超长字符串，高效利用了周期性，是线性动态规划中结合状态机与循环检测的经典题目。