参考答案及解析

题目1：KMP算法

判断题：1.√ 2.√ 3.√
选择题：4.A 5.C
解析：KMP算法通过预处理模式串构建next数组，匹配失败时利用next数组跳过不必要的比较。

题目2：字符串分割

判断题：1.√ 2.√ 3.×
选择题：4.B 5.A
解析：使用istringstream和getline可以方便分割字符串，if (!token.empty())会过滤空字符串。

题目3：字符串反转

判断题：1.√ 2.√ 3.√
选择题：4.A 5.B
解析：从右向左扫描，找到每个单词的边界，然后拼接到结果中。

题目4：最长公共前缀

判断题：1.√ 2.√ 3.√
选择题：4.A 5.C
解析：算法不断缩短前缀直到找到公共前缀，最坏情况需要比较所有字符串的所有字符。

题目5：字符串压缩

判断题：1.√ 2.√ 3.√
选择题：4.A 5.A
解析：只有连续字符数大于1时才添加计数，保证压缩后字符串更短。

题目6：字符串转整数

选择题：1.A 2.B 3.A 4.B 5.A
解析：需要处理前导空格、正负号和溢出情况，遇到非数字字符停止转换。

题目7：最长回文子串

选择题：1.A 2.A 3.C 4.B 5.C
解析：使用动态规划，dp[i][j]记录子串i-j是否为回文，通过状态转移方程求解。

题目8：字符串排列检查

选择题：1.A 2.A 3.B 4.A 5.C
解析：使用滑动窗口和频率数组，检查s2中是否存在与s1字符频率相同的子串。

题目9：最长无重复字符子串

选择题：1.B 2.A 3.A 4.A 5.C
解析：使用滑动窗口，记录字符最后出现位置，遇到重复时更新窗口起始位置。

题目10：字符串相加

选择题：1.B 2.B 3.A 4.A 5.A
解析：模拟手工加法，从低位到高位逐位相加，注意进位处理。

字符串算法专题总结

字符串处理是编程中的基础且重要的问题，本专题涵盖了字符串匹配、分割、反转、压缩、转换、搜索等常见操作。

核心知识点：

1. KMP算法：高效的字符串匹配算法，通过预处理模式串优化匹配过程
2. 字符串分割：使用流或指针操作处理字符串分割
3. 动态规划：用于解决最长回文子串等复杂问题
4. 滑动窗口：高效解决子串、子数组问题
5. 大数运算：通过字符串处理大整数运算

解题技巧：

• 注意边界条件和特殊输入（空字符串、空格等）
• 考虑时间复杂度和空间复杂度的平衡
• 利用字符串特性优化算法（如字符集有限时使用数组代替哈希表）
• 掌握常见的字符串处理函数和技巧