# 1. KMP 与朴素匹配的复杂度对比中朴素算法最坏 O(n·m)（如 'aaaa...b' 对 'aaaa...a'），KMP 如何通过 next 数组避免回溯降到 O(n+m)？ A 主串指针在失配时需要回退到失配位置的前一个字符 B 主串指针从不回退，模式串指针通过 next 数组跳跃，总复杂度 O(n+m) ✓ 正确答案 C next 数组记录了模式串后缀中最长公共前缀的长度，用于跳跃主串指针 D KMP 在最好情况下比朴素算法慢，因为需要额外构建 next 数组
# 2. 字符串的基本操作集合（查找、比较、子串、拼接）与复杂度？ A 循环中用 StringBuilder 拼接 N 个字符总复杂度为 O(n) 摊还 ✓ 正确答案 B Java 7 之后 substring 是 O(1)，因为它共享底层数组 C 循环中用 + 拼接 N 个字符总复杂度是 O(n)，因为每次操作都是 O(1) D hashCode 每次调用都重新计算，复杂度 O(n)
# 3. KMP 的 next 数组为什么能保证 O(n+m)，失配时最长公共前后缀如何避免重复比较，给出构建示例？ A next[i] 表示前缀 P[0..i] 中既做前缀又做后缀的最长长度（不含自身） ✓ 正确答案 B 失配时主串指针回退到 next 值对应的位置继续匹配 C next[i] 表示模式串整体与文本串的最长匹配长度 D next 数组的构建需要 O(n·m) 时间
# 4. Z 算法（Z-function）如何在线性时间内求每个位置与前缀的最长匹配，与 KMP 的应用场景差异？ A Z 算法的复杂度是 O(n log n)，因为每次都要暴力扩展 B z[i] 表示位置 i 与字符串前缀的最长匹配长度，算法总体 O(n) ✓ 正确答案 C Z 算法不能用于子串查找，只能算前缀匹配 D Z 算法与 KMP 内部机制完全相同，只是名字不同
# 5. 字符串匹配的朴素算法与 KMP 的 next 数组中失配时如何利用已匹配前缀避免回溯？ A KMP 在失配时主串指针和模式串指针都回退 B KMP 失配时主串指针不变，模式串指针跳到最长公共前后缀位置继续比较 ✓ 正确答案 C 朴素算法因为没有 next 数组所以代码更复杂 D KMP 无法利用已匹配的前缀信息
# 6. 字符串与字符数组/字节流的边界差异（不可变、编码、索引）？ A String 是可变的，char[] 是不可变的 B Java 的 String 索引按 UTF-16 code unit 进行，遍历 emoji 可能遇到代理对 ✓ 正确答案 C 字符串索引与字节索引在任意编码下含义完全相同 D 字节流可以直接当作字符串处理，无需解码
# 7. 字符串基础操作（拼接、反转、子串）在算法题与工程中的典型应用？ A 工程中拼接大量字符串应使用 StringBuilder 避免 O(n²) 退化 ✓ 正确答案 B 大数相加用字符串拼接比用数组更高效 C 反转字符串必须借助额外数组，无法原地进行 D 子串操作在算法题中永远是最优的
# 8. 字符编码在序列化、I/O 与跨语言交互中的典型应用？ A 序列化时可以不指定编码，因为平台默认编码总是正确的 B 字节流与字符流之间通过指定 Charset 进行转换，应显式传参避免依赖默认编码 ✓ 正确答案 C 网络协议应使用平台默认编码以保持兼容 D 跨语言比较字符串无需考虑编码，内容相同即可
# 9. 正则表达式与字符串匹配算法（KMP、多模式）的适用边界？ A KMP 适合复杂通配符模式的匹配 B 正则表达式性能总是稳定的，适合所有场景 C 固定单模式精确匹配用 KMP 更可靠，动态复杂规则用正则 ✓ 正确答案 D AC 自动机只能匹配一个模式串
# 10. 正则表达式使用有哪些常见误区（贪婪回溯、锚点、转义）？ A 贪婪量词 `.*` 在嵌套结构上不会导致回溯问题 B 在 Java 中用正则匹配字面量 `.` 需写成 `\\.` ✓ 正确答案 C 正则默认从字符串开头匹配，无需锚点 D 字符类 `[abc]` 中的 `-` 永远不需要转义
# 11. 正则引擎的两种实现中 NFA 模拟（Thompson）与回溯（backtracking）在性能与表达能力上的差异，灾难性回溯如何产生？ A Thompson NFA 支持反向引用，回溯引擎不支持 B 灾难性回溯只影响性能，不影响安全 C Thompson NFA 复杂度是最坏 O(n·m²) D 回溯引擎最坏情况可能指数级，嵌套量词如 `(a+)+` 可触发灾难性回溯 ✓ 正确答案
# 12. 正则匹配的核心概念中字符类、量词、分组与回溯？ A 量词 `*` 默认是非贪婪，匹配尽可能少 B 回溯是引擎在贪婪匹配失败后回退尝试其他可能的过程 ✓ 正确答案 C 分组 `(?:...)` 会捕获匹配内容供后续引用 D 字符类 `[a-z]` 只能匹配单个字符，不能与量词组合
# 13. 字符串操作有哪些常见误区（+=性能、索引越界、编码混淆）？ A 循环中 `s += "x"` 拼接 N 次总复杂度是 O(n)，因为每次操作都是 O(1) B Java 中 `==` 适合比较字符串内容是否相等 C 遍历含 emoji 的字符串时，每字符恰好占一个 char D 循环拼接应使用 StringBuilder 以避免 O(n²) 性能退化 ✓ 正确答案
# 14. 字符编码（ASCII/UTF-8/UTF-16）的差异与选型边界？ A UTF-8 兼容 ASCII 且无字节序问题，适合网络与文件存储 ✓ 正确答案 B UTF-8 是定长编码，每字符固定 4 字节 C UTF-16 没有字节序问题，无需 BOM D ASCII 覆盖所有 Unicode 码点
# 15. 字符编码处理有哪些常见误区（BOM、截断、非法字节）？ A 按字节硬截断子串可能切断多字节字符的中间字节，产生非法字节 ✓ 正确答案 B UTF-8 BOM 不会影响字符串比较，可以忽略 C 遇到非法字节时，解码器总是自动识别并正确修复 D 不同编码间转换只需按字节直接拼接即可
# 16. UTF-8 编码的核心概念中码点、字节序列、变长编码？ A UTF-8 是变长编码，ASCII 码点占 1 字节，后续字节以 "10" 开头可自同步 ✓ 正确答案 B UTF-8 每个字符固定占 4 字节 C UTF-8 需要用 BOM 才能区分字节序 D UTF-8 无法表示 BMP 之外的字符
# 17. 正则匹配在日志解析、输入校验、文本提取中的典型应用？ A 正则只能用于匹配，不能用于提取或替换 B 输入校验只能用正则，无法用其他方式 C 日志解析中可用正则配合捕获组提取时间戳、级别等结构化字段 ✓ 正确答案 D 正则替换一定比手写字符串操作慢
# 18. 正则表达式到 NFA 的 Thompson 构造中每个语法构造只引入常数个新状态，ε-转移如何合并，NFA 模拟为何能保证线性时间？ A 每个正则构造引入的状态数随正则长度线性增长，但单个构造引入的状态数是常数 ✓ 正确答案 B ε-转移需要消费一个字符才能到达另一状态 C NFA 模拟单个字符的复杂度是 O(m²)，m 为状态数 D Thompson 构造无法表达并集与闭包
