字符串基础题单

从字符与单词处理、回文和自定义排序开始，逐步过渡到字符串哈希、Trie、KMP 和 Manacher。

0 / 0 已完成

字符串基础题单

字符串入门先解决“如何表示和扫描字符串”，再学习“如何快速判断两个字符串的关系”。不要在还没有掌握下标、切片和边界处理时直接背 KMP 模板。

一、字符与单词处理

重点是字符分类、大小写、空格、单词边界和字符串长度。先把输入处理写稳定。

二、回文、括号与字符串构造

这一组练习双指针、栈和字符串比较。注意区分“修改字符串”和“只判断是否满足条件”。

三、Trie 与字符串集合

当题目反复询问“某个前缀是否出现”或“某个单词是否存在”时，Trie 比逐个字符串比较更自然。先做应用题，再看模板。

四、KMP 作为算法桥接

KMP 不必作为第一节，但它是从“暴力匹配”走向“利用已知匹配信息”的第一道字符串算法题。

五、回文串与 Manacher

Manacher 把每个位置作为回文中心统一处理，在 O(n) 时间内求出所有奇回文和偶回文的半径。先掌握半径数组的含义，再做需要统计或拼接两个回文串的应用题。

六、字符串哈希

字符串哈希把前缀信息编码成数值，使子串比较可以在 O(1) 或 O(log n) 时间完成。先掌握单串子串判等，再处理不同子串计数和二分答案。

七、AC 自动机

AC 自动机可以把 Trie 上的多个模式串匹配合并为一次扫描。学习时先理解 fail 指针和字典树上的失配转移，再处理模式串出现次数。

八、后缀数组

后缀数组把所有后缀按字典序排列，配合 LCP 可以统一处理子串排序、最长重复子串和不同子串问题。先掌握倍增排序，再做一个完整应用。

九、后缀自动机

后缀自动机压缩了一个字符串的所有子串信息。入门阶段先理解 endpos 等价类和状态转移，再做第 k 小子串或循环匹配。

暂不放入入门题单

后缀树、广义后缀自动机、多串后缀数组和复杂多模哈希应另建进阶题单。它们需要更稳定的前缀函数、Trie、哈希和复杂度基础。