LeetCode214最短回文串

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1：
输入：s = “aacecaaa”
输出：“aaacecaaa”
示例 2：

输入：s = “abcd”
输出：“dcbabcd”

提示：
0 <= s.length <= 5 * 104
s 仅由小写英文字母组成

分析

我们可以将s分成两部分s1+s2，其中s1是回文，假定前面增加的字符串是s0。因为s0+s1+s2是回文，所以s0和s2是逆序。要想s0最短，就要s2最短,也就是s1最长。那么此题的本质就是：求s是回文的最长前缀。如果s不存在回文前缀，则认为s1为空。求出s1后，再求s0和s2，并返回s0+s1+s2。
求回文至少有两种办法：一，枚举回文中心，时间复杂度O(n^2)。本题会超时。二，马拉车算法，时间复杂度O(n)。比较复杂，过些天专门写篇博文介绍马拉车算法。建议将马拉车算法封装成类。

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;

}

};