罗罗编程学习记录
本页内容 展开查看

02.2.2.3 字符串匹配 KMP/RK 与回文

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.2 字符串与哈希表

02.2.2.3-001 朴素字符串匹配怎么做?复杂度多少?

一句话结论

主串每个位置尝试与模式串逐字符比对,失配则主串前进一位重新开始;最坏 O(n·m),模式串与主串前缀相似时退化明显。

概念解释

  • n:主串长度,m:模式串长度。
  • 失配回退:主串起点右移,模式串归零。
  • 重复比较已扫描前缀。

原理流程

  1. 枚举主串起点 i。
  2. 逐字符比较模式串。
  3. 失配 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 数组记录失配后模式串位置。
  • 主串单调前进。

原理流程

  1. 预处理模式串求 next。
  2. 匹配中失配按 next 回退模式串。
  3. 主串指针不后退。

代码 / 图示

朴素:失配 → 主串 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 个字符组成的子串,最长相等真前缀与真后缀的长度;失配时据此把模式串右移。

概念解释

  • 真前缀:不含整体的前缀。
  • 真后缀:不含整体的后缀。
  • 最长相等:重叠部分长度。

原理流程

  1. 对每个 j 求最长前后缀相等长度。
  2. 失配时已匹配前缀可作为新起点。
  3. 跳转不丢失已匹配信息。

代码 / 图示

模式串 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:前缀匹配长度。
  • 回退:不等时沿已有 π 继续找更短前缀。

原理流程

  1. π[0]=0,j=0。
  2. i 从 1 扫描。
  3. 相等 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。

原理流程

  1. i、j 从 0 开始。
  2. 相等双进。
  3. 不等 j 回退;j=0 仍不等则 i++。
  4. 命中返回起点。

代码 / 示例

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 总量有界。
  • 预处理:π 构造同构线性。
  • 空间:模式串长度。

原理流程

  1. i 最多 n 步。
  2. j 递增不超过 n,回退抵消递增。
  3. 合计 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 表的工程优化。

概念解释

  • 冗余跳转:跳转后字符相等仍会失配。
  • 优化:链式回退到不同字符。
  • 不改变渐进量级。

原理流程

  1. 按 next 求跳转位置。
  2. 比较跳转位与当前位字符。
  3. 相同则继续沿 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]。

原理流程

  1. 求前缀函数。
  2. 计算候选周期 p。
  3. 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 能被该值整除时成立;否则最小重复表示需要补足字符,具体按题目口径。

概念解释

  • 循环节:重复单元。
  • 前缀函数给出最长重叠。
  • 整除性校验完整性。

原理流程

  1. 求末尾前缀函数值。
  2. 候选节长 p。
  3. 整除则 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 简单。

概念解释

  • 多项式哈希:字符加权求和。
  • 滚动:移出首位、加入末位,增量更新。
  • 哈希相等为候选,再验串防冲突。

原理流程

  1. 算模式串哈希。
  2. 主串首窗哈希。
  3. 滑动更新,哈希相同则逐字符确认。

代码 / 示例

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 的幂次。

原理流程

  1. 预计算幂次。
  2. 首窗哈希。
  3. 滑动: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) 比较。
  • 最坏:碰撞集中,验串累积。
  • 概率口径:非确定性最坏保证。

原理流程

  1. 滚动更新哈希。
  2. 哈希不同直接跳过。
  3. 哈希相同再验串。

代码 / 图示

平均: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 位相等。
  • 双指针内移。
  • 过滤规则可前置。

原理流程

  1. l=0,r=n-1。
  2. 比较并内移。
  3. 不一致返回 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 个。

概念解释

  • 奇回文:中心一个字符。
  • 偶回文:中心两字符间隙。
  • 扩展:对称相等继续。

原理流程

  1. 枚举中心。
  2. 左右扩展记录长度。
  3. 更新最长起止。

代码 / 示例

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) 空间。

概念解释

  • 单个字符本身是回文。
  • 扩展成功一层新增一个回文。
  • 奇偶两类中心分别计。

原理流程

  1. 枚举中心。
  2. 扩展成功计数加一。
  3. 累计总数。

代码 / 示例

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] 始终是回文;两侧相等才继续外扩,不等则该中心的最大回文已确定;不变量保证计数与长度正确。

概念解释

  • 初始:单字符或相邻两字符。
  • 保持:对称相等。
  • 终止:越界或不等。

原理流程

  1. 中心初始化回文区间。
  2. 两侧相等则扩大。
  3. 不等停止,记录区间。

代码 / 图示

中心 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] 为真;按区间长度填表;详见动态规划分册。

概念解释

  • 状态:区间回文性。
  • 转移:两端相等且内部回文。
  • 初始化:单字符真,两字符相等真。

原理流程

  1. 按长度递增填表。
  2. 两端相等查内部。
  3. 收集回文区间。

代码 / 图示

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 前缀函数线性求解。

概念解释

  • 拼接:原串接反串。
  • 前缀函数:末尾最长前后缀。
  • 后缀对应反串前缀,即原串回文前缀。

原理流程

  1. 拼接隔离串。
  2. 求前缀函数。
  3. 末尾值为答案长度。

代码 / 图示

t = s + "#" + reverse(s)
π[末] = 最长回文前缀长度

常见误区

  • 误区:不加分隔符;正解:防止前后缀越界混合。
  • 误区:直接枚举前缀判回文;正解:KMP 线性更优。

追问

  • Q:最短回文(在前补字符)? A:先求最长回文前缀,剩余反转补前。
  • Q:后缀同理吗? A:对称构造即可。

02.2.2.3-019 三种匹配/回文方法怎么选型?

一句话结论

短模式串朴素法足够;单模式精确匹配追求确定线性用 KMP;多模式或可接受概率用 RK;回文判断双指针,回文子串用中心扩展或区间 DP。

概念解释

  • 朴素:实现简单,小样本。
  • KMP:确定 O(n+m)。
  • RK:哈希候选,多模式方便。
  • 回文:对称结构专用方法。

原理流程

  1. 判断是匹配还是回文。
  2. 匹配看模式数量与精度要求。
  3. 回文按连续/子序列选方法。

代码 / 图示

单模式精确:KMP
多模式/简单实现:RK
回文判断:双指针
回文子串:中心扩展 / 区间 DP

常见误区

  • 误区:所有匹配都上 KMP;正解:小样本朴素法常数更小。
  • 误区:回文问题套 KMP;正解:回文利用对称性,框架不同。

追问

  • Q:模糊匹配/通配符用什么? A:动态规划或专门匹配算法,另述。
  • Q:多模式串匹配结构? A:AC 自动机,KMP 的多模式推广。

02.2.2.3-020 字符串匹配题有哪些边界与坑?

一句话结论

边界:模式串空、模式长于主串、全相同字符、首末命中、重复命中;坑:主串回退、哈希未验串、偶回文漏中心、越界取字符。

概念解释

  • 规模边界:长度比较。
  • 退化输入:重复字符放大失配。
  • 实现边界:下标越界。

原理流程

  1. 先判长度关系。
  2. 构造全相同与边界命中用例。
  3. 检查指针与边界条件。

代码 / 图示

p 为空 / p 长于 s
全 A 串
命中在首/尾
多重重叠命中

常见误区

  • 误区:模式长于主串仍进匹配循环;正解:先判长度返回未命中。
  • 误区:KMP 命中后未处理重叠;正解:按题目要求继续跳转收集。

追问

  • Q:空串匹配返回什么? A:按题面口径,常见为 0。
  • Q:大小写敏感吗? A:按题面,需要时先归一化。