企业官网建设流程全解析

• 教程
• 文档

本篇技术指南以公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列中 1668. 最大重复子字符串 的题解文档为核心，完整拆解这道入门级「序列 DP」题目：先给出直接截取子串比较的 $O(n \times m)$ 动态规划解法，再引入「字符串哈希」把子串比较降为 $O(1)$ 数值对比、整体优化到 $O(n + m)$。读完本文，你将掌握「以结尾位置为状态」的序列 DP 建模方法、字符串哈希预处理的完整套路，并理清「线性 DP」与「序列 DP」的本质差异，这些能力可直接复用到仓库中 Index/序列 DP.md 与 Index/字符串哈希.md 收录的十余道同类题目。

一、题目理解：重复值到底在求什么

1.1 题意与术语约定

题目给定两个字符串sequence与word：

• 若word连续重复k次形成的字符串是sequence的一个子字符串，则word的重复值为k；
• word的最大重复值是word在sequence中能取到的最大k；
• 若word根本不是sequence的子串，重复值为0。

注意关键限定词「连续重复」：即要求sequence中存在一段形如word + word + ... + word的连续片段，中间不能插入其他字符，这与「子序列」问题有本质区别。

为方便推导，原文档做了如下记号约定：将sequence记为ss，将word记为pp，两者长度分别记为n和m；同时把「字符串」以及「动规数组」的下标统一调整为从1开始。

1.2 三个示例与边界约束

题目约束如下：

• $1 \le sequence.length \le 100$
• $1 \le word.length \le 100$
• sequence和word都只包含小写英文字母

数据范围极小（均不超过 100），因此即便是 $O(n \times m)$ 的朴素做法也能轻松通过；本题的价值更多在于「入门序列 DP 建模」与「用字符串哈希优化找前驱」这两层递进思路，这也是仓库中该题被归类进 Index/序列 DP.md 和 Index/字符串哈希.md 两份索引的原因。

二、解法一：序列 DP（$O(n \times m)$）

2.1 状态定义与转移推导

原文档给出的做法是经典的「以结尾位置为状态」的序列 DP：

定义 $f[i]$ 为考虑以ss[i]结尾时的最大重复值。

之所以强调「以ss[i]结尾」，是因为本题要求的是连续重复片段，任何一段合法答案必然对应原串中某个以特定字符结尾、长度恰为 $k \times m$ 的连续子串；以结尾位置收束状态，可以保证转移时片段严格连续。

转移推导（关键一步）：由于pp的长度m已知，每次计算 $f[i]$ 时，从ss中截取以ss[i]为结尾、长度为m的后缀字符串sub，并与pp做匹配：

• 若两者相等，说明sub贡献了大小为1的重复度；
• 同时，由于sub紧贴在前一个合法片段的后面，这个重复度可以累加在 $f[i - m]$ 上（$f[i - m]$ 表示以ss[i - m]结尾时的最大重复值，即紧邻sub之前的那一段）。

于是得到状态转移方程：

$$ f[i] = f[i - m] + 1 $$

注意这里的下标设计是自洽的：sub占用的区间是ss[i - m + 1 .. i]，其前驱位置恰好是i - m，这正是「好好回想状态定义」后自然得到的转移关系——本题的拓扑序不是由数组下标线性给出的，而是由题目语义中「重复」这一结构决定的，这正是后文要展开的「序列 DP 需要自己找前驱」的特点。

边界与答案统计：

• 当i - m < 0时，无法截取长度为m的完整后缀，直接跳过；
• 每个 $f[i]$ 计算完毕后，用ans = Math.max(ans, f[i])维护全局最大值；
• 初始时所有 $f[i] = 0$，若pp从未作为子串出现过，答案自然保持为0，与题意「不是子串则重复值为 0」吻合。

2.2 完整代码

原文档给出了 Java、TypeScript、Python 三个版本的实现，内容如下：

Java 代码：

class Solution { public int maxRepeating(String ss, String pp) { int n = ss.length(), m = pp.length(), ans = 0; int[] f = new int[n + 10]; for (int i = 1; i <= n; i++) { if (i - m < 0) continue; if (ss.substring(i - m, i).equals(pp)) f[i] = f[i - m] + 1; ans = Math.max(ans, f[i]); } return ans; } }

TypeScript 代码：

function maxRepeating(ss: string, pp: string): number { let n = ss.length, m = pp.length, ans = 0 const f = new Array<number>(n + 10).fill(0) for (let i = 1; i <= n; i++) { if (i - m < 0) continue if (ss.substr(i - m, i) == pp) f[i] = f[i - m] + 1 ans = Math.max(ans, f[i]) } return ans }

Python 代码：

class Solution: def maxRepeating(self, ss: str, pp: str) -> int: n, m, ans = len(ss), len(pp), 0 f = [0] * (n + 10) for i in range(1, n + 1): if i - m < 0: continue if ss[i - m:i] == pp: f[i] = f[i - m] + 1 ans = max(ans, f[i]) return ans

一处实用的语言细节：TypeScript 版中ss.substr(i - m, i)的第二参数是「截取长度」而非结束下标（与 Java 的substring(begin, end)、Python 的切片ss[i - m : i]语义不同），严格对应题意应使用ss.slice(i - m, i)或ss.substring(i - m, i)，此处保留原文档写法便于对照三份实现，实际提交时建议按目标语言的切片语义核对一遍。

2.3 复杂度分析

• 时间复杂度：$O(n \times m)$。外层循环共 $n$ 个状态，每次转移需要 $O(m)$ 生成子串并比较；
• 空间复杂度：$O(n)$。仅需一个长度 $O(n)$ 的动规数组f（实现中额外开了n + 10的冗余空间）。

三、解法二：字符串哈希优化（$O(n + m)$）

3.1 瓶颈定位

解法一的转移瓶颈非常明确：每次都需要花费 $O(m)$ 的复杂度来生成子串并进行字符串比较。在 $n, m \le 100$ 的数据范围下这不是问题，但一旦把题目推广到更长字符串，$O(n \times m)$ 就不可接受了。

优化思路（原文档的核心手法）：把「生成子串 + 逐字符比较」这一 $O(m)$ 操作，替换为「数值哈希比较」这一 $O(1)$ 操作。具体来说：

1. 将ss与pp拼接得到完整字符串s = ss + pp；
2. 以 $O(n + m)$ 复杂度预处理出s的哈希数组h与次方数组p；
3. 从前往后检查ss，若「某个以ss[i]结尾、长度为m的后缀子串哈希值」与「pp字符串的哈希值」相等，说明该位置命中一次pp，找到前驱状态值 $f[i - m]$ 即可进行转移。

3.2 哈希预处理的底层原理

字符串哈希的核心思想是用一个多项式数值近似表示一个字符串，从而把「子串是否相等」转化为「两个整数是否相等」。预处理公式为（下标从 1 开始）：

$$ h[i] = h[i - 1] \times P + s[i], \qquad p[i] = p[i - 1] \times P $$

其中P为进制基数。任意区间子串s[l .. r]的哈希值可通过前缀哈希在 $O(1)$ 内得到：

$$ hash(s[l..r]) = h[r] - h[l - 1] \times p[r - l + 1] $$

在原文档的 Java 实现中，P取1313131，哈希值用long存储（利用 64 位整型自然溢出取模）；Python 实现中P = 131并显式对MOD = 987654321取模。两者都是「字符串哈希」这一技术在不同语言下的常见落地形态，仓库中 1044. 最长重复子串（字符串哈希 + 二分）与 686. 重复叠加字符串匹配（字符串哈希 / KMP）均使用了完全同构的h/p预处理套路，可作为对照阅读。

pp哈希值的获取技巧：由于我们把ss和pp拼接成了s，pp恰好占据s的末尾m个字符，因此pp的哈希值就是：

$$ phash = h[N] - h[N - m] \times p[m] $$

其中N为拼接后的总长度。这样我们不需要额外为pp单独算一遍哈希，直接复用s的哈希数组即可。

3.3 转移过程

在动规主循环中，对于每个i：

• 若i - m < 0，跳过；
• 否则计算以ss[i]结尾、长度为m的子串哈希：cur = h[i] - h[i - m] * p[m]；
• 若cur == phash，说明这一段就是pp，执行f[i] = f[i - m] + 1；
• 维护全局最大值ans。

整体效果正如原文档所总结：通过 $O(n + m)$ 复杂度的预处理，将转移过程中「$O(m)$ 的子串截取与字符串比较」替换成「$O(1)$ 的数值对比」，整体复杂度从 $O(n \times m)$ 下降到 $O(n + m)$。

3.4 完整代码

Java 代码：

class Solution { public int maxRepeating(String ss, String pp) { int n = ss.length(), m = pp.length(), ans = 0; int[] f = new int[n + 10]; String s = ss + pp; int P = 1313131, N = s.length(); long[] h = new long[N + 10], p = new long[N + 10]; p[0] = 1; for (int i = 1; i <= N; i++) { h[i] = h[i - 1] * P + s.charAt(i - 1); p[i] = p[i - 1] * P; } long phash = h[N] - h[N - m] * p[m]; for (int i = 1; i <= n; i++) { if (i - m < 0) continue; long cur = h[i] - h[i - m] * p[m]; if (cur == phash) f[i] = f[i - m] + 1; ans = Math.max(ans, f[i]); } return ans; } }

Python 代码：

class Solution: def maxRepeating(self, ss: str, pp: str) -> int: n, m, ans = len(ss), len(pp), 0 f = [0] * (n + 10) s = ss + pp P, N, MOD = 131, len(s), 987654321 h, p = [0] * (N + 10), [0] * (N + 10) p[0] = 1 for i in range(1, N + 1): h[i] = (h[i - 1] * P + ord(s[i - 1])) % MOD p[i] = (p[i - 1] * P) % MOD phash = (h[N] - h[N - m] * p[m]) % MOD for i in range(1, n + 1): if i - m < 0: continue cur = (h[i] - h[i - m] * p[m]) % MOD if cur == phash: f[i] = f[i - m] + 1 ans = max(ans, f[i]) return ans

3.5 复杂度与正确性边界

• 时间复杂度：$O(n + m)$，预处理 $O(n + m)$，转移过程 $O(n)$；
• 空间复杂度：$O(n + m)$，需要存储哈希数组h、次方数组p与动规数组f。

关于哈希碰撞的说明：字符串哈希本质是以数值近似替代字符串比较，理论上存在不同字符串映射到同一哈希值的概率（碰撞）。在本题 $n, m \le 100$ 的小数据范围下，配合大进制基数（Java 的long溢出取模、Python 的大模数取模）碰撞概率极低，是工程与竞赛场景中可接受的近似做法；若追求严格正确，可改用双哈希或直接比较原字符串兜底。仓库 472. 连接词 的题解中对哈希碰撞处理有专门讨论（提及双哈希与「记录哈希值对应了哪些字符串」两种更稳妥的替代方案），可作延伸参考。

四、从本题看「线性 DP」与「序列 DP」的本质区别

原文档在总结部分专门辨析了这两个高频概念，这也是本题作为入门题最值得吸收的「元知识」：

线性 DP：通常强调「状态转移所依赖的前驱状态」由给定数组直接提供，即拓扑序由原数组天然给出——更直白地说，一般形如 $f[i][...]$ 依赖于 $f[i - 1][...]$。因此线性 DP 的复杂度由「状态数量（维度数）」直接决定，转移关系是「送上门」的。

序列 DP：通常需要结合题意自己寻找前驱状态，即需要自行寻找拓扑序关系。本题就是典型例子：转移并非沿下标线性进行，而是由「重复」语义决定——只有当前后缀等于pp时，前驱才是 $f[i - m]$，这个「跳跃式」的前驱关系必须从题意中自己提炼出来。

由此可以得出一个重要推论：序列 DP 的复杂度由「状态数 + 找前驱」的复杂度共同决定。这也直接导致了序列 DP 玩法丰富，常常可以结合其他知识点出题来优化「找前驱」这一操作——通常手段是利用某些性质（如本题的哈希化整为零），或是利用数据结构（如 1218. 最长定差子序列 用哈希表记录值域状态快速找前驱、Index/序列 DP.md 中多题结合二分/哈希/排序优化转移）。

五、仓库延伸：同类题目与索引体系

本题收录于本仓库 LeetCode/1661-1670/ 目录，并同时出现在三份专题索引中，可作为系统刷题路线的入口：

• Index/序列 DP.md：收录 139、334、354、472、583、1218、1668、1691、1713、1751 等二十余道序列 DP 题目，每行均带题解链接与推荐指数；
• Index/字符串哈希.md：收录 187、472、686、1044、1668、面试题 01.09 等字符串哈希题目；
• Index/线性 DP.md：收录 10、44、53、91、198、403、1220 等线性 DP 题目，可与上文的「线性 vs 序列」辨析对照阅读。

与本题高度相关的四道姊妹题，建议按序精读：

六、调试与自测建议

由于题目数据范围极小（$n, m \le 100$），建议在本地 IDE 或 LeetCode 在线评测中按以下方式验证两份解法的一致性：

1. 边界用例：word长度大于sequence时（如sequence = "a",word = "ab"），所有i - m < 0成立，答案应为0；
2. 完全重叠覆盖：如sequence = "aaaa",word = "aa"，最大重复值应为2（"aaaa" = "aa" + "aa"，注意允许片段之间首尾相接、无空余）；
3. 部分命中干扰：如sequence = "ababc",word = "abc"，只有一次命中，答案为1；
4. 两解法对拍：随机生成小写字符串，对比序列 DP 版与字符串哈希版的输出是否始终一致，可用于验证哈希实现的边界（尤其是p[0] = 1的初始化与phash的区间计算）。

综上，本题虽然标记为「简单」，却同时覆盖了「序列 DP 状态设计」「以结尾位置建模」「字符串哈希预处理」「找前驱的复杂度优化」四层核心能力，是仓库「刷穿 LeetCode」系列中性价比极高的一道入门综合题。

• 教程
• 文档