214. 最短回文串
- 題目描述
- 思路分析
- 代碼實作
題目描述
點這里
思路分析
回文串問題轉化為KMP
問題等價于求最長回文前綴，構造翻轉后等價于求KMP的next陣列
代碼實作
class Solution {
public:
string shortestPalindrome(string s) {
string t(s.rbegin(),s.rend());
int n=s.size();
s=' '+s+'#'+t;
vector<int> ne(n*2+2);
for(int i=2,j=0;i<=n*2+1;i++){
while(j&&s[i]!=s[j+1]) j=ne[j];
if(s[i]==s[j+1]) j++;
ne[i]=j;
}
int len=ne[n*2+1];
string left=s.substr(1,len),right=s.substr(1+len,n-len);
return string(right.rbegin(),right.rend())+left+right;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/356343.html
標籤：其他