# 最短回文串
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1：
输入：s = "aacecaaa"
输出："aaacecaaa"
示例 2：
输入：s = "abcd"
输出："dcbabcd"
提示：
0 <= s.length <= 5 * 104s 仅由小写英文字母组成
## template
```cpp
#include
using namespace std;
class Solution
{
public:
string shortestPalindrome(string s)
{
string rev(s);
reverse(rev.begin(), rev.end());
;
string combine = s + "#" + rev;
vector lps(combine.length(), 0);
int remove = getLPS(combine, lps);
string prepend = rev.substr(0, rev.length() - remove);
return prepend + s;
}
int getLPS(string s, vector &lps)
{
int j = 0, i = 1;
while (i < s.length())
{
if (s[i] == s[j])
{
lps[i] = j + 1;
i++;
j++;
}
else
{
if (j != 0)
{
j = lps[j - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
return lps[lps.size() - 1];
}
};
```
## 答案
```cpp
```
## 选项
### A
```cpp
```
### B
```cpp
```
### C
```cpp
```