题目
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入: "aacecaaa"
输出:"aaacecaaa"
示例 2:
输入:"abcd"
输出:"dcbabcd"
思路解析
这题考虑把字符串s分成s1和s2两部分，即s=s1+s2，其中s1为回文串，s2不是回文串，那么构成的最短回文串就是reverse(s2.begin(),s2.end())+s。所以这道题最大的难点就是找出从起始位置开始的最长回文子串。关于最长回文子串的解法可以参考最长回文子串(https://blog.csdn.net/lv1224/article/details/81051875)，
方法一
DP做法是要考虑所有可能的回文串，但是这题只需要考虑从起始位置开始的字符串就可以了，所以直接考虑从起始位置开始的所有字符串，判断是否是回文串即可，注意从大往小考虑，如果构成回文串，剩下的就可以不用考虑
代码
class Solution {
public:
string shortestPalindrome(string s) {
int n=s.size(),maxlen=0;
if(n<=1) return s;
int r=n-1;
while(r>0){
int i=0,j=r;
while(j>i&&s[i]==s[j]){
i++;j--;
}
if(i>=j) break;
r--;
}
string s1=s.substr(r+1,n-r-1);
reverse(s1.begin(),s1.end());
return s1+s;
}
};
方法二 中心扩展
直接采用中心扩展来做，会有一个case过不了，这里有一个小技巧。中心点不需要从起始位置开始，也不需要遍历所有的，只要找到最大的就可以停止了。n=s.size()，那么回文串最大就是s本身，所以只需要从n/2的位置开始往左遍历即可，一旦找到从起始位置开始的回文串，就可以停止寻找，得出答案。这样可以减少程序运行时间。
class Solution {
public:
string shortestPalindrome(string s) {
int n=s.size(),maxlen=0;
if(n<=1) return s;
//这里会有一个小技巧
for(int i=n/2;i>=0&&maxlen<=0;i--){
int r=1;
while(i-r>=0&&i+r<n&&s[i-r]==s[i+r]) r++;
if(maxlen<2*r-1&&i-r+1==0)
maxlen=2*r-1;
if(i>=n||s[i]!=s[i+1]) continue;
r=1;
while(i-1>=0&&i+1+r<n&&s[i-r]==s[i+1+r]) r++;
if(maxlen<2*r&&i-r+1==0)
maxlen=2*r;
}
string s1=s.substr(maxlen,n-maxlen);
reverse(s1.begin(),s1.end());
return s1+s;
}
};
方法三 马拉车算法
static const auto __ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
string shortestPalindrome(string s) {
int ns=s.size();
if(ns<=1) return s;
string tmp(2*ns+1,'*');
for(int i=0;i<ns;i++) tmp[2*i+1]=s[i];
int pos=0,curlen=0,n=tmp.size();
int maxr=0;
vector<int> slen(n,0);
for(int i=0;i<n;i++){
int mi=2*pos-i,r=mi>=0?slen[mi]:0;
if(i<pos+curlen&&i+r<pos+curlen){
slen[i]=slen[mi];
continue;
}
if(i>=pos+curlen) r=1;
else r=pos+curlen-i;
while(i+r<tmp.size()&&i-r>=0&&(tmp[i+r]==tmp[i-r])) r++;
slen[i]=r-1;
pos=i;
curlen=r-1;
if(maxr<=r-1&&i-slen[i]==0){
maxr=r-1;
}
if(i+r==tmp.size()) break;
}
string s1=s.substr(maxr,ns-maxr);
reverse(s1.begin(),s1.end());
return s1+s;
}
};
方法四 KMP解法
这一种方法是比较巧妙的，r=s;reverse(r.begin(),r.end());t=s+"#"+r，要求s从起始位置开始的最长回文子串，就可以转换成t的最长前缀后缀问题；
比如s=ccab,r=bacc,t=ccab#bacc，那么s中最长的回文串cc也就是t中前缀cc。
再比如s=aacecaaa,r=aaacecaa,t=aacecaaa#aaacecaa，则最长回文子串是aacecaa，而t中前缀为aacecaa。
这里要特别注意需要加上#，这个很重要，防止s=aaa的时候出现错误。
所以这题其实就演变成KMP算法，求解next数组。具体原理见KMP算法(链接：https://blog.csdn.net/v_july_v/article/details/7041827/)
代码;
class Solution {
public:
string shortestPalindrome(string s) {
string r=s;
reverse(r.begin(),r.end());
string t=s+"#"+r;
int n=t.size();
vector<int> idx(n,-1);
for(int i=1;i<n;i++){
int p=idx[i-1];
while(p!=-1&&t[i]!=t[p+1])
p=idx[p];
if(p==-1) idx[i]=t[i]==t[0]?0:-1;
else idx[i]=p+1;
}
string tmp=s.substr(idx[n-1]+1,s.size()-idx[n-1]-1);
reverse(tmp.begin(),tmp.end());
return tmp+s;
}
};
