由一道困难leetcode引发的思考
前几天leetcode的一道困难级别的每日一题再次让我感受到真正的聪明人擅长的是把困难的问题转换成简单的问题，而不是死磕难题。
这道题目的链接：https://leetcode-cn.com/problems/shortest-palindrome/solution/
题目
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
1 | 输入: "aacecaaa" |
示例 2:
1 | 输入: "abcd" |
解题思路
我不知道有没有小伙伴会和我一样，bfs，dfs，dp之类的用多了，就会往那个方向考虑，但是思考了半天好像也没有什么好的方法，于是去看了眼题解，恍然大悟。
要学会把问题转化
简单一句话来说，就是找到现有字符串s的最长回文前缀s‘，那么把剩下的s - s’倒序放到s的开头，就是最短的回文串了。
这是具体的官方证明逻辑：https://leetcode-cn.com/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/
这样一来，一个寻找最短回文串的问题就变成了简单的寻找最长回文前缀，看到这里的时候我是真的绝的有种茅塞顿开的感觉。
接下来就简单了，怎么找回文前缀。
寻找最长回文前缀
暴力法
最简单的暴力解法，可以依次判断从从 0 开始到 i 的子串是不是回文的，i 从 s.length - 1 到 0.
KMP算法
KMP算法是用来计算两个字符串之间重叠的部分的。
假设字符串s的倒叙是s‘，那么通过KMP算法得到的重叠部分就应该是s的最长回文前缀。
KMP算法
对于KMP算法的解释，阮一峰老师的这篇博客讲的比较清晰
如果还有什么地方会有疑惑的话，可能就是为什么：移动位数 = 已匹配的字符数 - 对应的部分匹配值
那么我们就要搞懂：
部分匹配值代表了什么
- "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
－ "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－ "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－ “ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A”，长度为1；
－ “ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB”，长度为2；
－ "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，“ABCDAB"之中有两个"AB”，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。
- 假设已匹配字符位数是m，就代表模式串的前m位与匹配串的【i, i + m - 1】是相同的， i是本次匹配开始的位置。
- 而此时的部分匹配值是n，那就代表模式串的前n位与【i, i + m - 1】的后n位是相同的。
所以移动m - n位可以跳过去匹配那些不可能相同的位。
参考链接：
https://leetcode-cn.com/problems/shortest-palindrome/
https://www.cxyxiaowu.com/2665.html
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html