信息技术大学
字符串
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
字符串
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
反转与遍历技巧
字符串不可变语言里先转数组再玩：双指针原地交换是基本功。
原地反转
左右指针交换着向中间走，O(1) 空间
按词反转
先整体反转再逐词反转，二次反转法
回文系列（中心扩展/双指
回文有对称轴：奇偶两种中心往外扩，2n−1 个中心一次遍历找最长。
中心扩展
n 个字符中心加 n−1 个间隙中心，向外扩
双指针验证
首尾对撞比对，判回文 O(n)
Manacher
线性求最长回文，了解思路即可
KMP 与字符串匹配
匹配失败不回头：next 数组记住「已匹配部分的最长相等前后缀」。
暴力匹配
失配全回退重比，最坏 O(nm)
next 数组
模式串每个前缀的最长相等前后缀长度
主串不回退
失配跳到 next 位置继续，整体 O(n+m)
异位词分组
异位词排序后同形：把排序结果当哈希 key，一扫分组。
排序作 key
同字母异序词排序后相同，O(nk log k)
计数作 key
26 位字母计数值作 key，免排序更快
窗口变体
找 s 中 p 的异位子串：定长窗口计数比对
本节要点
- ✓原地反转：左右指针交换走
- ✓回文找中心，2n−1 个往外扩
- ✓KMP：next 数组保主串不回头
- ✓异位词：排序或计数作哈希 key
延伸主题：手写中心扩展最长回文实现一次 KMP 匹配
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1中心扩展为什么是 2n−1 个中心？
参考答案奇长度回文的中心是字符本身，共 n 个；偶长度回文的中心在两字符之间，共 n−1 个。两类都要枚举，漏掉间隙中心会错过 abba 型回文。
2KMP 的 next 数组本质在记录什么？
参考答案记录模式串每个前缀的「最长相等前后缀」：失配说明已匹配部分内部有可复用的重叠结构，跳到 next 位置就是无回退地复用这段信息，主串指针永不后退。
3异位词分组用排序 key 与计数 key，各适合什么规模？
参考答案排序 key 简单直观，代价 O(k log k) 乘在词长上，词短量大时很合适；计数 key O(k) 更快但要规范化字母集，超大输入或含 Unicode 时需改造。