给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入: "aacecaaa"
输出: "aaacecaaa"
示例 2:
输入: "abcd"
输出: "dcbabcd"
代码
class Solution {
public:
string shortestPalindrome(string s) {
string r = s;
reverse(r.begin(), r.end());
string t = s + "#" + r;
vector<int> next(t.size(), 0);
for (int i = 1; i < t.size(); ++i) {
int j = next[i - 1];
while (j > 0 && t[i] != t[j]) j = next[j - 1];
next[i] = (j += t[i] == t[j]);
}
return r.substr(0, s.size() - next.back()) + s;
}
};