题目
给定一个字符串 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; }
};
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版
