#1668.最大重复子字符串

LeetCode 原题链接

给你一个字符串 sequence 和一个字符串 word，请返回 word 在 sequence 中最大的重复次数。

重复次数 k 表示字符串 word 连续重复 k 次后得到的字符串 word * k 是 sequence 的子字符串。

例如，sequence = "ababc"、word = "ab" 时，"ab" 是 sequence 的子字符串，但 "abab" 也是，所以答案是 2。

#1.dp 数组含义

定义一维数组 dp：

dp[i] 表示以 sequence[i - 1] 结尾的、由 word 重复组成的最长字符串的重复次数。

这里的 i 表示 sequence 的前 i 个字符，因此 dp[i] 对应 sequence[i - 1] 这个结尾位置。

题目要求整个 sequence 中的最大重复次数，所以最终答案是所有 dp[i] 中的最大值。

#2. 确定状态转移方程

如果当前位置不足以容纳一个完整的 word，或者 sequence 从 i - word.length 到 i - 1 的这一段不等于 word，就不能以当前位置结尾形成重复字符串：

dp[i] = 0

如果这一段等于 word，说明可以把一个 word 接到前面的重复字符串后面：

dp[i] = dp[i - word.length] + 1

原因是前一个状态表示紧挨着当前 word 之前的最长重复次数，当前又匹配出了一个完整的 word，所以重复次数加 1。

#3.dp 数组如何初始化

dp[0] = 0，表示空字符串中没有 word 的重复。

其余位置初始化为 0。如果某个位置无法匹配完整的 word，保持为 0 即可。

当 word 为空字符串时，题目约束通常保证 word 非空；若单独处理该边界，可以直接返回 0，避免取模或截取时产生无意义结果。

#4. 确定遍历顺序

dp[i] 依赖 dp[i - word.length]，所以必须让 i 从小到大遍历：

for (let i = word.length; i <= sequence.length; i++) {
  // 计算 dp[i]
}

这样计算当前状态时，前面紧邻的重复字符串状态已经计算完成。

#5. 举例打印dp 数组

以：

sequence = "ababcab"
word = "ab"

为例，逐个检查以每个位置结尾的长度为 2 的片段：

最终：

dp = [0, 0, 1, 0, 2, 0, 0, 1]

最大值为 2，对应的重复子字符串是 "abab"，所以答案是 2。如果 sequence = "ababab"，对应的 dp[6] = dp[4] + 1 = 3，答案就是 3。

#6. 代码实现

/**
 * @param {string} sequence
 * @param {string} word
 * @return {number}
 */
var maxRepeating = function (sequence, word) {
  if (word.length === 0) return 0;

  const dp = new Array(sequence.length + 1).fill(0);
  let answer = 0;

  for (let i = word.length; i <= sequence.length; i++) {
    const start = i - word.length;

    if (sequence.slice(start, i) === word) {
      dp[i] = dp[start] + 1;
      answer = Math.max(answer, dp[i]);
    }
  }

  return answer;
};

时间复杂度为 O(n * m)，其中 n 是 sequence.length，m 是 word.length；空间复杂度为 O(n)。