# 题目大意
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
如：s = "aacecaaa"，输出"aaacecaaa"，输入"abcd",输出"dcbabcd"
# 吐槽
今日的美好心情被一道hard所击败，这道题确实有一丢丢难，官方题解更是tmd晦涩难懂，所以我才自己记录一下。
首先官方题解的前面分析还是很有用的，大概理一下，对于没思路的时候也可以慢慢来，首先我们应该可以想到不管给出的字符串是何种形式，我们都可以将其翻转过后（再去除最后一个字符，这样可以少一个字符）再到原字符串上得到一个回文串，如“abcd”,可以得到”bcdabcd“，但是如果这样做的话，可能得到的字符串很长，不是我们想要的最优答案，但从这里可以看出来，最长的回文串的长度小于2n（n是原字符串的长度）
# 分析
设原字符串为s，再设一个字符串s1，使得s' = s1 +(拼接符) s 是一个回文字符串，上面说了s1的长度肯定小于s，那么可以将s'分成两个字串 s2, s3，前一部分s2的长度是|s| - |s1|，剩下的部分s3为另一个字串（长度为|s1|)，那么可以将s' 拆分成 s1 + s2 +s3，其中s2+s3 = s。 要想这个字符串s'为回文串，那么必s1的倒序和s3相同并且s2是本身是一个回文串，那么问题就明朗了，要想s1最短，即想s3最短，即希望s2最长（s2 + s3 = s（原串））同时s2还必须是回文串，那么问题就变成了找s中最长的回文串前缀。找到后，再将剩余的部分翻转拼接到前面即可。
可以暴力，暴力就是遍历字符串的每一个位置，然后判断此前缀是否是回文串即可，这个不谈
另外，字符串，前缀等关键词很容易将 KMP算法联系起来，因为kmp中的next数组就是找一个数组的前缀和后缀相同的部分的，所以这里可以参照kmp算法。
# 官方题解
官方就是用了kmp算法，但由于kmp本身的复杂性，官方又将kmp算法修改了一下，不是经常写的童鞋很难看懂。 官方大概的思想是，将s作为模式串，将s翻转过后的字符串s^作为文本串匹配，然后用kmp算法进行匹配，但要注意这里不一定能匹配成功，我们就是需要知道遍历完文本串后模式串的下标i，这个下标就可以代表前缀和后缀匹配的字符个数，后续再根据这个进行切割和拼接即可，上面的文字可能有点抽象，而且原理不太明显，面举个栗子解释下：
比如输入：s = "abac" ,其翻转过后的字符串s' = "caba"，我们求出s的next数组，然后去比较：
Text : "caba"
pattern: "abac"
这样我们就可以看出，实际上就是用pattern的前缀去匹配text的后缀，因为text串是pattern串翻转过去的，因此如果存在前缀等于后缀的情况，那么就可以说明是原字符串的前缀有回文串，而且一定能找到最大的前缀文串，上面这个栗子中，遍历完整个text串后，pattern串的遍历指针变成了i = 2，说明有长度为3的前缀回文串，后续切割即可，原理就是这样，kmp的代码还是不太好写，因为你要保证pattern的前缀必须匹配的是tex的后缀，因此在匹配过程中还可能出现回溯操作，如 text = “abceba”， pattern = “abecba”，这样的话，开始两个字符ab能够匹配，但是这并不是text的后缀串，因此后续回回溯pattern字串指针。
```cpp
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.size();
vector<int> fail(n, -1);
for (int i = 1; i < n; ++i) {
int j = fail[i - 1];
while (j != -1 && s[j + 1] != s[i]) {
j = fail[j];
}
if (s[j + 1] == s[i]) {
fail[i] = j + 1;
}
}
int best = -1;
for (int i = n - 1; i >= 0; --i) {
while (best != -1 && s[best + 1] != s[i]) {
best = fail[best];
}
if (s[best + 1] == s[i]) {
++best;
}
}
/* 上述的for循环变换了一下kmp，我这里补充一个kmp教科书上的经典写法
int i = n-1;//这里是倒序
int best = -1;
while(i >= 0){
if(best == -1 || s[best] == s[i]){
i--;
best++;
} else {
best = fail[best] //这类的fail就是next数组。
}
}
*/
string add = (best == n - 1 ? "" : s.substr(best + 1, n));
reverse(add.begin(), add.end());
return add + s;
}
};
```
# 自己的一点想法
官方题解不太好想，就翻转过后再匹配的思想确实比较难想，我自己在做的过程中想到了next数组不是本身就是用来求前后缀是否相同的字符串长度吗，那为啥不能将字符串翻转过后再拼接上原字符串，对这个新的字符串求next数组呢，最终的next数组的值就是前缀等于后缀的长度呀，这样理论上是可以的。
如： s = “abac”, s' = "caba"， 拼接后的新字符串为"abaccaba"，这样找出来的最终next数组的最后一个值（即整个字符串的前缀等于后缀的长度）为3，即原字符串前面存在三个字符长度的回文串。
但是这样会有一个问题，就是拼接后的字符串长度为2n，这就有可能会使得next数组的最后一个值大于n，这样后续就没有办法切割了，如下面一个栗子：
s = "aabba" , s' = "abbaa"，拼接后的新字符串为“aabbaabbaa”
观察这个新串，它整个串的前缀等于后缀串的字符为6（“aabbaa”)，这就大于了原字符串长度（5）,主要原因就是这个翻转的串和原来的串做拼接的时候，恰好接上了，这里我也有点不知道咋形容，反正就是导致了这个前缀等于后缀的长度大于了原字符串的长度，这就使得后续没法计算。
一个解决办法是，拼接的时候插入一个没有出现过的字符，如 “#”，这样结果是“aabba#abbaa”，它的作用就是防止前缀等于后缀的串长度大于n，可以看出，当前缀大于n的时候就会带上这个“#”字符，这样后面就不可能有能够匹配的后缀，这就避免了刚才哪个问题，这个也是看别人的想法的! 确实帅。自己写的代码页超过了80%
class Solution {
public:
vector<int> getNext(string s){
int n = s.size();
vector<int>next(n+1,-1);
int j = -1, i = 0;
while(i < n - 1){ // < n 可能会越界
if(j == -1 || s[j] == s[i]){
i++;
j++;
if(s[i] == s[j]){ // 改进的next数组
next[i] = next[j];
} else{
next[i] = j;
}
} else {
j = next[j];
}
}
return next;
}
string shortestPalindrome(string s) {
if(s == ""){
return "";
}
string s1 = s;
reverse(s1.begin(),s1.end());
if (s1 == s){
return s;
}
s1 = s + "#" + s1;
vector<int> next = getNext(s1);
string add = s.substr(next[next.size()-1],s.size());
reverse(add.begin(),add.end());
return add + s;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 总结
我看评论，大部分人对于kmp算法都是一看就会，一写就忘，我也是这样，从学数据结构开始，反反复复看了几十次了吧，但是每次都记不住。我开始也以为是我自己理解不深刻的原因，后来感觉也理解了还是不一定能写出来。我觉得主要有两个方面的原因，第一个是kmp算法确实用得少，就字符串匹配的时候用一下，日常中很少遇到字符串匹配，就算遇到了一般量不大都是暴力，只有做算法题的时候才会刻意去用，而且算法题考kmp的题页确实少！任何东西只有使用频率少了都会忘，更别说一个算法了。第二个原因是kmp算法很精妙，代码更加精妙，有那种很精炼的感觉，就像提纯一样，提到最后，确实更精炼了，但是你很难看出它的本质，写kmp代码也是如此，下手写的时候总是感觉少了点什么，总感觉逻辑性不是很强，很多时候是在记忆中去搜寻哈哈哈哈，也有可能是自己确实太菜了，先记录下吧。