教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南以公众号「宫水三叶的刷题日记」刷穿 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的重复值为kword的最大重复值是word在sequence中能取到的最大k若word根本不是sequence的子串重复值为0。注意关键限定词「连续重复」即要求sequence中存在一段形如word word ... word的连续片段中间不能插入其他字符这与「子序列」问题有本质区别。为方便推导原文档做了如下记号约定将sequence记为ss将word记为pp两者长度分别记为n和m同时把「字符串」以及「动规数组」的下标统一调整为从1开始。1.2 三个示例与边界约束输入输出解释sequence ababcword ab2abab是ababc的子字符串sequence ababcword ba1ba是子串但baba不是sequence ababcword ac0ac不是ababc的子字符串题目约束如下$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 Arraynumber(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)$ 操作。具体来说将ss与pp拼接得到完整字符串s ss pp以 $O(n m)$ 复杂度预处理出s的哈希数组h与次方数组p从前往后检查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拼接成了spp恰好占据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 ans3.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 序列」辨析对照阅读。与本题高度相关的四道姊妹题建议按序精读题目关联点139. 单词拆分同为字符串上的序列 DP但找前驱依赖字典是本题的「放宽版」472. 连接词序列 DP 字符串哈希的进阶组合还涉及哈希碰撞处理686. 重复叠加字符串匹配方向相反已知重复次数上限求匹配字符串哈希 / KMP 双解1044. 最长重复子串字符串哈希 二分的典型应用预处理套路与本题完全一致六、调试与自测建议由于题目数据范围极小$n, m \le 100$建议在本地 IDE 或 LeetCode 在线评测中按以下方式验证两份解法的一致性边界用例word长度大于sequence时如sequence a,word ab所有i - m 0成立答案应为0完全重叠覆盖如sequence aaaa,word aa最大重复值应为2aaaa aa aa注意允许片段之间首尾相接、无空余部分命中干扰如sequence ababc,word abc只有一次命中答案为1两解法对拍随机生成小写字符串对比序列 DP 版与字符串哈希版的输出是否始终一致可用于验证哈希实现的边界尤其是p[0] 1的初始化与phash的区间计算。综上本题虽然标记为「简单」却同时覆盖了「序列 DP 状态设计」「以结尾位置建模」「字符串哈希预处理」「找前驱的复杂度优化」四层核心能力是仓库「刷穿 LeetCode」系列中性价比极高的一道入门综合题。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐字符串哈希全解从滚动哈希原理到 LeetCode 重复子串/连接词/字符串轮转实战LogicStack-LeetCode 刷穿系列字符串哈希全解从滚动哈希原理到 LeetCode 重复子串/连接词/字符串轮转实战LogicStack LeetCode 刷穿系列 字符串哈希Strin教程文档LogicStack-LeetCode 刷穿系列3. 无重复字符的最长子串——哈希表 双指针滑动窗口全解LogicStack LeetCode 刷穿系列3. 无重复字符的最长子串——哈希表 双指针滑动窗口全解 本篇技术指南以 LogicStack LeetC教程文档抖音批量下载怎么搞douyin-downloader 免费实操指南抖音批量下载怎么搞douyin downloader 免费实操指南 想把喜欢的创作者主页作品全部存到本地douyin downloader 是一款免费开源的网页爬虫CLI上一篇终极Scrapy-Redis架构原理详解从分布式爬虫到数据存储的完整指南下一篇qmlweb vs 传统Qt为什么浏览器端QML引擎更适合Web开发创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/9 1:36:03 · 阅读 1.2k LogicStack-LeetCode 题解：LeetCode 1668「最大重复子字符串」的序列 DP 与字符串哈希双解法
教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南以公众号「宫水三叶的刷题日记」刷穿 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的重复值为kword的最大重复值是word在sequence中能取到的最大k若word根本不是sequence的子串重复值为0。注意关键限定词「连续重复」即要求sequence中存在一段形如word word ... word的连续片段中间不能插入其他字符这与「子序列」问题有本质区别。为方便推导原文档做了如下记号约定将sequence记为ss将word记为pp两者长度分别记为n和m同时把「字符串」以及「动规数组」的下标统一调整为从1开始。1.2 三个示例与边界约束输入输出解释sequence ababcword ab2abab是ababc的子字符串sequence ababcword ba1ba是子串但baba不是sequence ababcword ac0ac不是ababc的子字符串题目约束如下$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 Arraynumber(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)$ 操作。具体来说将ss与pp拼接得到完整字符串s ss pp以 $O(n m)$ 复杂度预处理出s的哈希数组h与次方数组p从前往后检查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拼接成了spp恰好占据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 ans3.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 序列」辨析对照阅读。与本题高度相关的四道姊妹题建议按序精读题目关联点139. 单词拆分同为字符串上的序列 DP但找前驱依赖字典是本题的「放宽版」472. 连接词序列 DP 字符串哈希的进阶组合还涉及哈希碰撞处理686. 重复叠加字符串匹配方向相反已知重复次数上限求匹配字符串哈希 / KMP 双解1044. 最长重复子串字符串哈希 二分的典型应用预处理套路与本题完全一致六、调试与自测建议由于题目数据范围极小$n, m \le 100$建议在本地 IDE 或 LeetCode 在线评测中按以下方式验证两份解法的一致性边界用例word长度大于sequence时如sequence a,word ab所有i - m 0成立答案应为0完全重叠覆盖如sequence aaaa,word aa最大重复值应为2aaaa aa aa注意允许片段之间首尾相接、无空余部分命中干扰如sequence ababc,word abc只有一次命中答案为1两解法对拍随机生成小写字符串对比序列 DP 版与字符串哈希版的输出是否始终一致可用于验证哈希实现的边界尤其是p[0] 1的初始化与phash的区间计算。综上本题虽然标记为「简单」却同时覆盖了「序列 DP 状态设计」「以结尾位置建模」「字符串哈希预处理」「找前驱的复杂度优化」四层核心能力是仓库「刷穿 LeetCode」系列中性价比极高的一道入门综合题。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐字符串哈希全解从滚动哈希原理到 LeetCode 重复子串/连接词/字符串轮转实战LogicStack-LeetCode 刷穿系列字符串哈希全解从滚动哈希原理到 LeetCode 重复子串/连接词/字符串轮转实战LogicStack LeetCode 刷穿系列 字符串哈希Strin教程文档LogicStack-LeetCode 刷穿系列3. 无重复字符的最长子串——哈希表 双指针滑动窗口全解LogicStack LeetCode 刷穿系列3. 无重复字符的最长子串——哈希表 双指针滑动窗口全解 本篇技术指南以 LogicStack LeetC教程文档抖音批量下载怎么搞douyin-downloader 免费实操指南抖音批量下载怎么搞douyin downloader 免费实操指南 想把喜欢的创作者主页作品全部存到本地douyin downloader 是一款免费开源的网页爬虫CLI上一篇终极Scrapy-Redis架构原理详解从分布式爬虫到数据存储的完整指南下一篇qmlweb vs 传统Qt为什么浏览器端QML引擎更适合Web开发创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考