02.2.2.3 字符串匹配 KMP/RK 与回文
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.2 字符串与哈希表
02.2.2.3-001 朴素字符串匹配怎么做?复杂度多少?
一句话结论
主串每个位置尝试与模式串逐字符比对,失配则主串前进一位重新开始;最坏 O(n·m),模式串与主串前缀相似时退化明显。
概念解释
- n:主串长度,m:模式串长度。
- 失配回退:主串起点右移,模式串归零。
- 重复比较已扫描前缀。
原理流程
- 枚举主串起点 i。
- 逐字符比较模式串。
- 失配 i++,重新比对。
代码 / 示例
int naive(String s, String p) {
int n = s.length(), m = p.length();
for (int i = 0; i <= n - m; i++) {
int j = 0;
while (j < m && s.charAt(i + j) == p.charAt(j)) j++;
if (j == m) return i;
}
return -1;
}
常见误区
- 误区:朴素匹配一定 O(n);正解:最坏 O(nm)。
- 误区:主串失配后模式串保留位置;正解:朴素法模式串回到起点。
追问
- Q:什么输入最坏? A:主串与模式串大量前缀相同,如
AAAA…B。 - Q:m 很小时朴素法够用吗? A:常数小,可接受;m 大才需 KMP/RK。
02.2.2.3-002 KMP 解决朴素匹配的什么问题?
一句话结论
KMP 利用模式串自身的前后缀信息,失配时主串指针不回退,模式串跳到已匹配前缀对应的位置继续,避免重复比较。
概念解释
- 已匹配前缀:模式串头部与尾部相同部分。
- 跳转表:next 数组记录失配后模式串位置。
- 主串单调前进。
原理流程
- 预处理模式串求 next。
- 匹配中失配按 next 回退模式串。
- 主串指针不后退。
代码 / 图示
朴素:失配 → 主串 i++,模式串 j=0
KMP:失配 → j = next[j],i 不动
常见误区
- 误区:KMP 让主串跳得更快;正解:核心是主串不回退,模式串智能回退。
- 误区:KMP 预处理可省;正解:next 表是前提。
追问
- Q:KMP 适用场景? A:单模式串精确匹配,主串不可重复扫描代价高。
- Q:多模式串用什么? A:AC 自动机,属进阶结构。
02.2.2.3-003 next 数组(前缀函数)定义是什么?
一句话结论
next[j](前缀函数 π[j])表示模式串前 j 个字符组成的子串,最长相等真前缀与真后缀的长度;失配时据此把模式串右移。
概念解释
- 真前缀:不含整体的前缀。
- 真后缀:不含整体的后缀。
- 最长相等:重叠部分长度。
原理流程
- 对每个 j 求最长前后缀相等长度。
- 失配时已匹配前缀可作为新起点。
- 跳转不丢失已匹配信息。
代码 / 图示
模式串 ABAB
π: A→0, AB→0, ABA→1, ABAB→2
失配在第 4 位:跳到长度 2 对应位置
常见误区
- 误区:next 存的是失配位置下标;正解:存最长相等前后缀长度,下标换算配套。
- 误区:前后缀可以是串整体;正解:真前后缀不含自身。
追问
- Q:π[0] 是多少? A:单字符无真前后缀,为 0。
- Q:next 与前缀函数是一回事吗? A:口径略有偏移,本质都是前后缀长度表。
02.2.2.3-004 next 数组怎么构造?
一句话结论
双指针:j 记录当前前缀长度,i 扫描模式串;相等则 j++ 记录 π[i],不等则 j 回退到 π[j-1];O(m) 构造。
概念解释
- i:后缀扫描位置。
- j:前缀匹配长度。
- 回退:不等时沿已有 π 继续找更短前缀。
原理流程
- π[0]=0,j=0。
- i 从 1 扫描。
- 相等 j++ 写 π[i];不等 j=π[j-1] 直到可比较。
代码 / 示例
int[] buildNext(String p) {
int m = p.length();
int[] pi = new int[m];
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && p.charAt(i) != p.charAt(j)) j = pi[j - 1];
if (p.charAt(i) == p.charAt(j)) j++;
pi[i] = j;
}
return pi;
}
常见误区
- 误区:不等时 j 直接归 0;正解:先沿 π 回退,保留可匹配前缀。
- 误区:pi 赋值在 j++ 之前;正解:先比较再写长度。
追问
- Q:构造为什么 O(m)? A:j 最多随 i 递增 m 次,回退总量有界。
- Q:前缀函数回退链是什么? A:
π[j-1]逐级缩短到可匹配前缀。
02.2.2.3-005 KMP 匹配流程怎么写?
一句话结论
主串 i 与模式串 j 同步扫描;相等双进;失配 j=π[j-1] 回退模式串;j 达到 m 即命中;主串 i 不回退。
概念解释
- 匹配位:(i, j)。
- 失配跳转:按前缀函数。
- 命中:j == m。
原理流程
- i、j 从 0 开始。
- 相等双进。
- 不等 j 回退;j=0 仍不等则 i++。
- 命中返回起点。
代码 / 示例
int kmp(String s, String p) {
int[] pi = buildNext(p);
int n = s.length(), m = p.length(), j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && s.charAt(i) != p.charAt(j)) j = pi[j - 1];
if (s.charAt(i) == p.charAt(j)) j++;
if (j == m) return i - m + 1;
}
return -1;
}
常见误区
- 误区:失配时 i 也回退;正解:KMP 主串不回退。
- 误区:命中后未继续可找多匹配;正解:题目要求全部命中时按 π[m-1] 继续跳转。
追问
- Q:匹配多次怎么收集? A:命中后
j=π[j-1]继续扫主串。 - Q:空模式串? A:按口径返回 0 或特殊值。
02.2.2.3-006 KMP 复杂度怎么推?
一句话结论
预处理 O(m),匹配 O(n),整体 O(n+m);主串每字符只前进一次,模式串 j 递增与回退总量有界;空间 O(m) 存 next。
概念解释
- 线性:i 单调增,j 总量有界。
- 预处理:π 构造同构线性。
- 空间:模式串长度。
原理流程
- i 最多 n 步。
- j 递增不超过 n,回退抵消递增。
- 合计 O(n+m)。
代码 / 图示
预处理:O(m)
匹 配:O(n)
空 间:O(m)
常见误区
- 误区:KMP 匹配是 O(n·m);正解:主串不回退,线性。
- 误区:next 空间可省;正解:需保存模式串前后缀信息。
追问
- Q:KMP 比 RK 快吗? A:量级都线性,常数与场景不同,RK 实现更简单。
- Q:模式串很长? A:next 表 O(m) 空间,可接受。
02.2.2.3-007 nextval 优化是什么?
一句话结论
若失配位置跳转后字符仍与当前字符相同,会再失配;nextval 直接跳到更远处的不同字符,减少无效比较;属于 next 表的工程优化。
概念解释
- 冗余跳转:跳转后字符相等仍会失配。
- 优化:链式回退到不同字符。
- 不改变渐进量级。
原理流程
- 按 next 求跳转位置。
- 比较跳转位与当前位字符。
- 相同则继续沿 next 跳转。
代码 / 图示
next: 失配 → j=next[j]
nextval: 若 p[j]==p[next[j]],继续跳直到不同
常见误区
- 误区:nextval 改变 KMP 复杂度;正解:只减常数比较次数。
- 误区:面试必须手写 nextval;正解:理解前缀函数与跳转思想即可。
追问
- Q:为什么会出现冗余跳转? A:模式串重复段导致前后缀字符相同。
- Q:现代实现还用 nextval 吗? A:核心仍靠前缀函数,优化细节按实现。
02.2.2.3-008 判断重复子串(LC 459)怎么做?
一句话结论
若串由某子串重复构成,则长度 n 是周期长度倍数,且 s 与 s.substring(周期) 对齐匹配;用前缀函数:n % (n-π[n-1]) == 0 即存在重复周期。
概念解释
- 周期 p:前缀重复覆盖全串。
- π[n-1]:最长相等前后缀长度。
- 最小周期 = n - π[n-1]。
原理流程
- 求前缀函数。
- 计算候选周期 p。
- n 能被 p 整除即重复构成。
代码 / 示例
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
int[] pi = new int[n];
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && s.charAt(i) != s.charAt(j)) j = pi[j - 1];
if (s.charAt(i) == s.charAt(j)) j++;
pi[i] = j;
}
int p = n - pi[n - 1];
return pi[n - 1] > 0 && n % p == 0;
}
常见误区
- 误区:枚举所有子串逐个拼接比较;正解:前缀函数线性判定。
- 误区:π[n-1]=0 时也判周期;正解:无前后缀则不重复。
追问
- Q:最小重复周期怎么求? A:
n - π[n-1],前提整除。 - Q:
s+s去掉首尾找 s 的方法? A:另一经典判断,原理是周期串 doubled 后包含自身。
02.2.2.3-009 最短循环节怎么求?
一句话结论
最短循环节长度 = n - π[n-1],当 n 能被该值整除时成立;否则最小重复表示需要补足字符,具体按题目口径。
概念解释
- 循环节:重复单元。
- 前缀函数给出最长重叠。
- 整除性校验完整性。
原理流程
- 求末尾前缀函数值。
- 候选节长 p。
- 整除则 p 为最短节长。
代码 / 图示
"ababab":π[末]=4,p=6-4=2,节长 "ab"
常见误区
- 误区:不校验整除直接取 p;正解:不整除说明末尾未完整覆盖。
- 误区:循环节与子串概念混淆;正解:循环节要求重复拼接覆盖全串。
追问
- Q:周期串移位匹配? A:KMP 在 doubled 串上查找原串。
- Q:节长为 n 意味着什么? A:无更小重复单元。
02.2.2.3-010 RK 滚动哈希的思想是什么?
一句话结论
把模式串与主串各窗口映射为哈希值,窗口滑动时增量更新哈希;哈希相等再比对字符串确认;平均 O(n+m),实现比 KMP 简单。
概念解释
- 多项式哈希:字符加权求和。
- 滚动:移出首位、加入末位,增量更新。
- 哈希相等为候选,再验串防冲突。
原理流程
- 算模式串哈希。
- 主串首窗哈希。
- 滑动更新,哈希相同则逐字符确认。
代码 / 示例
hash(s[l..r]) = Σ s[i]·b^(r-i)
滑动:移出高位,加入低位,乘幂更新
常见误区
- 误区:哈希相等即命中;正解:存在碰撞,必须再比对原串。
- 误区:每次窗口重算哈希;正解:滚动增量更新才线性。
追问
- Q:哈希碰撞概率? A:取决于模数与基数,双哈希降低概率。
- Q:RK 适合多模式吗? A:模式哈希入集合,主串窗口逐个查。
02.2.2.3-011 滚动哈希怎么计算与更新?
一句话结论
取基数 b 与模数 mod,H = (H·b + c) mod mod;窗口右移时减去离开字符的高位权重,加入新字符,整体取模维护。
概念解释
- 多项式展开:高位权重大。
- 模运算:控制哈希值范围。
- 权重:预处理 b 的幂次。
原理流程
- 预计算幂次。
- 首窗哈希。
- 滑动:
H = (H - out·b^(m-1))·b + in,取模。
代码 / 示例
// 窗口长度 m,基数 b,模数 mod
long h = 0;
for (int i = 0; i < m; i++) h = (h * b + a[i]) % mod;
// 滑出 a[left],加入 a[right]
h = ((h - a[left] * pow[m - 1]) * b + a[right]) % mod;
常见误区
- 误区:减法后负数未转正;正解:取模后加 mod 再取模规范化。
- 误区:幂次未预处理;正解:滚动需高位权重,提前算好。
追问
- Q:模数选大质数? A:降低碰撞,超大数运算注意溢出用宽类型。
- Q:双哈希怎么做? A:两套基数模数并行,碰撞概率更低。
02.2.2.3-012 RK 的复杂度与冲突代价是什么?
一句话结论
平均 O(n+m);哈希碰撞时需逐字符比对,最坏所有窗口碰撞退化为 O(nm);工程上大模数/双哈希把碰撞概率压到极低。
概念解释
- 平均:哈希 O(1) 比较。
- 最坏:碰撞集中,验串累积。
- 概率口径:非确定性最坏保证。
原理流程
- 滚动更新哈希。
- 哈希不同直接跳过。
- 哈希相同再验串。
代码 / 图示
平均:O(n+m)
最坏:碰撞全中 → O(nm)
常见误区
- 误区:RK 有最坏线性保证;正解:概率性结构,最坏仍可能退化。
- 误区:哈希相等不用验串;正解:必须比对原串确认。
追问
- Q:KMP 与 RK 选型? A:追求确定线性选 KMP;实现简单、可接受概率选 RK。
- Q:二维网格匹配可用 RK 吗? A:可推广二维滚动哈希。
02.2.2.3-013 回文判断怎么做?
一句话结论
相向双指针比较对称位置,全部相等即回文;O(n) 时间 O(1) 空间;过滤字符与大小写规则按题目口径处理。
概念解释
- 对称:第 i 位与倒数第 i 位相等。
- 双指针内移。
- 过滤规则可前置。
原理流程
- l=0,r=n-1。
- 比较并内移。
- 不一致返回 false。
代码 / 示例
public boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
if (s.charAt(l++) != s.charAt(r--)) return false;
}
return true;
}
常见误区
- 误区:先反转再比较;正解:双指针 O(1) 额外空间。
- 误区:忽略大小写/过滤规则;正解:按题面归一化。
追问
- Q:数字字母混合? A:先过滤再比较,见 02.2.1.1 验证回文串。
- Q:回文整数? A:可反转后半段比较,避免转字符串。
02.2.2.3-014 最长回文子串(LC 5)中心扩展怎么做?
一句话结论
枚举每个中心(单字符与双字符两种),向两侧扩展直到不等;记录最长;O(n²) 时间 O(1) 空间;回文中心共 2n-1 个。
概念解释
- 奇回文:中心一个字符。
- 偶回文:中心两字符间隙。
- 扩展:对称相等继续。
原理流程
- 枚举中心。
- 左右扩展记录长度。
- 更新最长起止。
代码 / 示例
public String longestPalindrome(String s) {
int start = 0, max = 0;
for (int c = 0; c < s.length(); c++) {
int[] a = expand(s, c, c); // 奇
int[] b = expand(s, c, c + 1); // 偶
if (a[1] > max) { start = a[0]; max = a[1]; }
if (b[1] > max) { start = b[0]; max = b[1]; }
}
return s.substring(start, start + max);
}
int[] expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
return new int[]{l + 1, r - l - 1};
}
常见误区
- 误区:只枚举单字符中心;正解:偶回文中心在两字符之间。
- 误区:扩展边界不检查;正解:先判越界再取字符。
追问
- Q:Manacher 算法? A:O(n) 求最长回文,利用回文对称性预处理,属进阶。
- Q:DP 做法? A:
dp[i][j]表区间是否回文,O(n²) 空间 O(n²)。
02.2.2.3-015 回文子串计数(LC 647)怎么做?
一句话结论
中心扩展:每个中心向两侧扩展,每成功匹配一对即计一个回文;O(n²) 时间 O(1) 空间。
概念解释
- 单个字符本身是回文。
- 扩展成功一层新增一个回文。
- 奇偶两类中心分别计。
原理流程
- 枚举中心。
- 扩展成功计数加一。
- 累计总数。
代码 / 示例
public int countSubstrings(String s) {
int ans = 0;
for (int c = 0; c < s.length(); c++) {
ans += expandCount(s, c, c);
ans += expandCount(s, c, c + 1);
}
return ans;
}
int expandCount(String s, int l, int r) {
int cnt = 0;
while (l >= 0 && r < s.length() && s.charAt(l--) == s.charAt(r++)) cnt++;
return cnt;
}
常见误区
- 误区:只计最长回文;正解:所有回文子串都要计数。
- 误区:单字符未计入;正解:每个字符自身是回文。
追问
- Q:DP 怎么计数? A:
dp[i][j]为真时累加,O(n²)。 - Q:回文子序列计数? A:不要求连续,用 DP,见动态规划分册。
02.2.2.3-016 中心扩展法的不变量是什么?
一句话结论
扩展过程中 [l, r] 始终是回文;两侧相等才继续外扩,不等则该中心的最大回文已确定;不变量保证计数与长度正确。
概念解释
- 初始:单字符或相邻两字符。
- 保持:对称相等。
- 终止:越界或不等。
原理流程
- 中心初始化回文区间。
- 两侧相等则扩大。
- 不等停止,记录区间。
代码 / 图示
中心 c:[l, r] 回文
两侧 s[l-1]==s[r+1] → 扩大
否则停止
常见误区
- 误区:不等后还换方向继续;正解:回文一旦断开,该中心不再扩展。
- 误区:偶中心初始两字符不等;正解:不等则该偶回文长度为 0。
追问
- Q:多个中心重叠会重复计数吗? A:不同中心对应不同回文,不重复。
- Q:扩展长度怎么换算? A:奇/偶长度由初始中心决定。
02.2.2.3-017 回文相关 DP 状态怎么定义?
一句话结论
区间 DP:dp[i][j] 表示子串 [i,j] 是否回文;转移 s[i]==s[j] 且内部 dp[i+1][j-1] 为真;按区间长度填表;详见动态规划分册。
概念解释
- 状态:区间回文性。
- 转移:两端相等且内部回文。
- 初始化:单字符真,两字符相等真。
原理流程
- 按长度递增填表。
- 两端相等查内部。
- 收集回文区间。
代码 / 图示
dp[i][j] = (s[i]==s[j]) && (j-i<2 || dp[i+1][j-1])
常见误区
- 误区:按 i、j 同时递增填表;正解:依赖更短区间,按长度顺序。
- 误区:认为区间 DP 空间一定可省;正解:求全部回文需全表,只求最长可按长度滚动优化。
追问
- Q:中心扩展与 DP 谁快? A:同 O(n²),扩展法空间更省。
- Q:回文分割问题? A:判断回文用同构区间表,分割方案另套 DP/回溯。
02.2.2.3-018 最长回文前缀怎么求?
一句话结论
构造 s + '#' + reverse(s),求末尾前缀函数值,长度即最长回文前缀;KMP 前缀函数线性求解。
概念解释
- 拼接:原串接反串。
- 前缀函数:末尾最长前后缀。
- 后缀对应反串前缀,即原串回文前缀。
原理流程
- 拼接隔离串。
- 求前缀函数。
- 末尾值为答案长度。
代码 / 图示
t = s + "#" + reverse(s)
π[末] = 最长回文前缀长度
常见误区
- 误区:不加分隔符;正解:防止前后缀越界混合。
- 误区:直接枚举前缀判回文;正解:KMP 线性更优。
追问
- Q:最短回文(在前补字符)? A:先求最长回文前缀,剩余反转补前。
- Q:后缀同理吗? A:对称构造即可。
02.2.2.3-019 三种匹配/回文方法怎么选型?
一句话结论
短模式串朴素法足够;单模式精确匹配追求确定线性用 KMP;多模式或可接受概率用 RK;回文判断双指针,回文子串用中心扩展或区间 DP。
概念解释
- 朴素:实现简单,小样本。
- KMP:确定 O(n+m)。
- RK:哈希候选,多模式方便。
- 回文:对称结构专用方法。
原理流程
- 判断是匹配还是回文。
- 匹配看模式数量与精度要求。
- 回文按连续/子序列选方法。
代码 / 图示
单模式精确:KMP
多模式/简单实现:RK
回文判断:双指针
回文子串:中心扩展 / 区间 DP
常见误区
- 误区:所有匹配都上 KMP;正解:小样本朴素法常数更小。
- 误区:回文问题套 KMP;正解:回文利用对称性,框架不同。
追问
- Q:模糊匹配/通配符用什么? A:动态规划或专门匹配算法,另述。
- Q:多模式串匹配结构? A:AC 自动机,KMP 的多模式推广。
02.2.2.3-020 字符串匹配题有哪些边界与坑?
一句话结论
边界:模式串空、模式长于主串、全相同字符、首末命中、重复命中;坑:主串回退、哈希未验串、偶回文漏中心、越界取字符。
概念解释
- 规模边界:长度比较。
- 退化输入:重复字符放大失配。
- 实现边界:下标越界。
原理流程
- 先判长度关系。
- 构造全相同与边界命中用例。
- 检查指针与边界条件。
代码 / 图示
p 为空 / p 长于 s
全 A 串
命中在首/尾
多重重叠命中
常见误区
- 误区:模式长于主串仍进匹配循环;正解:先判长度返回未命中。
- 误区:KMP 命中后未处理重叠;正解:按题目要求继续跳转收集。
追问
- Q:空串匹配返回什么? A:按题面口径,常见为 0。
- Q:大小写敏感吗? A:按题面,需要时先归一化。