题目
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1：
输入：s = “aacecaaa”
输出：“aaacecaaa”
示例 2：
输入：s = “abcd”
输出：“dcbabcd”
提示：
0 <= s.length <= 5 * 104
s 仅由小写英文字母组成
2023年4月版
class Solution {
public:
string shortestPalindrome(string s) {
if (“” == s)
{
return “”;
}
m_c = s.length();
std::string s1 = Do(s);
std::string strAdd;
for (int i = s.length() - 1; i >= s1.length(); i–)
{
strAdd += s[i];
}
return strAdd + s;
}
string Do(const string& s)
{
vector next(m_c, -1);
for (int i = 1; i < m_c; i++)
{
int iNext = next[i - 1];
while ((-1 != iNext) && (s[iNext + 1] != s[i]))
{
iNext = next[iNext];
}
next[i] = (s[i] == s[iNext + 1]) ? iNext + 1 : iNext;
}std::string sRever(s.rbegin(), s.rend());
int i = 0, j = 0;
while ((i<m_c)&&(j<m_c))
{
while ((i < m_c) && (j < m_c) && (s[i] == sRever[j]))
{
i++;
j++;
}
if (i >= m_c - (j - i))
{
return s.substr(0, i);
}
if (j >= m_c)
{
return "";
}
if ((i > 0) && (next[i - 1] >= 0))
{
i = next[i - 1] + 1;
}
else
{
if (i > 0)
{
i = 0;
}
else
{
j++;
}
}
}
return s.substr(0,1);
}
int m_c;};
2023年8月版（马拉车）
class CKMP
{
public:
static vector Next(const string& s)
{
const int len = s.length();
vector vNext(len, -1);
for (int i = 1; i < len; i++)
{
int next = vNext[i - 1];
while ((-1 != next) &&(s[next + 1] != s[i]))
{
next = vNext[next];
}
vNext[i] = next + (s[next + 1] == s[i]);
}
return vNext;
}
};
class Solution {
public:
string shortestPalindrome(string s) {
vector next = CKMP::Next(s);
int n = s.length();
int preSameIndex = -1;
for (int i = n - 1; i >= 0; i–)
{
const auto& ch = s[i];
while ((-1 != preSameIndex) && (s[preSameIndex + 1] != ch))
{
preSameIndex = next[preSameIndex];
}
if (ch == s[preSameIndex + 1])
{
preSameIndex++;
}
}
string add = (preSameIndex == n - 1 ? “” : s.substr(preSameIndex + 1, n));
reverse(add.begin(), add.end());
return add + s;}};其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
我的其它课程
[]
()
测试环境
win7 VS2019 C++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版