Day14-字符串-最长回文子串
一 今天唠唠嗑
首先感谢大家的关注，以及仔细地阅读
后台有小伙伴私信说，希望增加一些栏目。这些建议我都会认真听取，等我闲下来的时候，一定把公众号功能丰富一些，比如自动回复，增加别的栏目什么的~
什么，你问我什么时候闲下来
然后今天也是初级字符串算法题的最后一篇了，难题和链表一样，所有模块算法题都过完一遍，再上难题~
前两天和朋友聊天，他们公司之前面了一位北航的实习生，ACM经历，然鹅最长回文子串都没写出来
那么今天，就来解决这道经典字符串算法题
二 上题！
Q：给定字符串s，若子串str是回文串，则成str是s的回文子串。求一个字符串的最长回文子串。
举例：对于s = “abbacdedctgbbgtabba”
回文子串有：“abba”，“cdedc”，“tgbbgt”
那么最长回文子串就是“tgbbgt”
有的要求长度，有的要求具体最长回文子串
本文将全部给出
三 冷静分析
单纯判断字符串是否回文，很简单，在这给出简单代码
//
// Created by renyi on 2019/6/19.
// 单纯判断一个字符串是否为回文串
//
#include <iostream>
#include <string>
using namespace std;
bool palindromeString(string s){
int i = 0;
int j = s.length() - 1;
while (i <= j){
if (s[i] == s[j]){
i += 1;
j -= 1;
} else{
return false;
}
}
return true;
}
int main(){
string a = "aba";
cout << palindromeString(a) << endl;
return 0;
}aba是回文的，那么运行结果
那么对于高了一个档次的，本题呢？
算法一：枚举s所有子串，满足回文的同时，满足最长
结果：O（N^3）n的立方，同学请你出门右转
算法二：遍历s的每个字符，（奇数）以该字符为中心，向左向右同时遍历，（偶数）以两个字符为中心，向左向右同时遍历，当不满足回文时停止，最终筛选最长回文串
结果：O（N^2）n的平方，嗯，还可以，那你完整写出来吧
算法三：Manacher算法，为最长回文子串而生，O（N），了解一下
一般人都能想到算法二，所以面试官八成不会打断你。但我们需要思考的是，能不能再优化？manacher算法就是在算法二的基础上，优化的：
即，在遍历每个字符时，对于第i个位置的回文串，和第j个位置的回文串，会不会有某种关系，从而降低时间复杂度？
manacher算法本身不难，但要结合画图，才好懂明白，可要画图的话，我画的实在不好，最重要的是，manacher算法相当成熟，大家可以自行百度它的图解，加深理解。我只叙述manacher的核心思路供大家参考：
1.算法二中，要处理奇数偶数的差别，实在让人讨厌，不如将原字符串变奇数个：
对每个字符的左右均插入#号，此时s中，n个元素变成了2n+1个，就是奇数个了，不用处理奇偶差别了。
2.在对s的遍历过程中
i是当前字符位置
center代表当前最长回文串的中心点
maxRight代表当前最长回文串的右边界
j，代码里用2*center - i代替，是i关于center的对称点
建立一个数组p，每个元素，即p[i]，存储以当前字符i为中心，最长回文串的长度
3.我们首先对p[i]的值界定一下：
当i > maxRight时，比当前最大回文串的右边界还靠右，我们没有更多的依据认为，以i为中心的最长回文串，有多长，即此时，界定p[i] = 1
当i < maxRight时，j作为i关于center的对称点，在i左边，则此时p[j]是已知的。且p[j] = p[i]，那我们先谨慎的界定此时p[i]取（p[j]，maxRight - i）两者最小值
4.界定完了之后，根据前后是否相等，相等即回文，累加p[i]的值
5.若i + p[i]，即当前字符下标，加上以当前字符为中心的最长回文串的长度，相加后的值，即以i为中心，最长回文串的右边界。若它大于maxRight，则更新maxRight为它，且更新center中心点，为i。
6.那么对于数组p[i]，它的最大值 - 1，就是最终的最长回文子串的长度了（每个字符为中心的最长回文串长度都在数组p里，最大的值，即为长度）
7.若求出具体子串，请参考我的代码即可
四 完整代码及注释
同时为了方便在代码中处理数组越界问题，在插入后的字符串最左边增加起始符号 '$'
//
// Created by renyi on 2019/6/20.
//
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string manacherMaxPalindromeString(string s){
string result = "";//带#号的最长回文串
string result_str = "";//最终的最长回文串
vector<char> tempStr;//字符数组，存储s加#号和$号后的字符串
tempStr.push_back('$');
for (int i = 0; i < s.length(); i++) {
tempStr.push_back('#');
tempStr.push_back(s[i]);
}
tempStr.push_back('#');
int center = 0;//当前最长回文串的中心点
int maxRight = 0;//当前最长回文串的右边界
int n = tempStr.size();
vector<int> p(n);//数组p，存储tempStr中以每个字符为中心点，最长回文串的长度
for (int i = 1; i < tempStr.size(); i++) {
string word = "";
if (maxRight > i){
p[i] = min(p[2 * center - i], maxRight - i);
} else{
p[i] = 1;
}
while (tempStr[i-p[i]] == tempStr[i+p[i]]){
p[i]++;
}
for (int j = i-p[i]+1; j <= i+p[i]-1; ++j) {
word += tempStr[j];
}
if (i + p[i] > maxRight){
maxRight = i + p[i];
center = i;
}
if (result.length() < word.length()){
result = word;
}
}
printf("result字符串为:%s, 需要去#号\n", result.c_str());
for (int k = 0; k < result.size(); k++) {
if (result[k] != '#'){
result_str += result[k];
}
}
return result_str;
}
int manacherMaxPalindromeLength(string s){
int max_length = 0;//最终最长回文串的长度
vector<char> tempStr;
tempStr.push_back('$');
for (int i = 0; i < s.length(); i++) {
tempStr.push_back('#');
tempStr.push_back(s[i]);
}
tempStr.push_back('#');
int center = 0;//当前最长回文串的中心点
int maxRight = 0;//当前最长回文串的右边界
int n = tempStr.size();
vector<int> p(n);//数组p，存储tempStr中，以每个字符为中心点，最长回文串的长度
for (int i = 1; i < tempStr.size(); i++) {//先对p[i]的值做个界定，即预处理
if (maxRight > i){
p[i] = min(p[2 * center - i], maxRight - i);
} else{
p[i] = 1;
}
while (tempStr[i-p[i]] == tempStr[i+p[i]]){//界定完了之后，算出实际的p[i]的值，即若前后相等，即回文，那么p[i]累加
p[i]++;
}
if (i + p[i] > maxRight){//更新右边界即中心点
maxRight = i + p[i];
center = i;
}
max_length = max(max_length, p[i] - 1);
}
return max_length;
}
int main(){
string string1 = "abbacdedctgbbgtabba";
string result_str = manacherMaxPalindromeString(string1);
int result_len = manacherMaxPalindromeLength(string1);
printf("最长回文字符串是: %s, 长度是: %d\n", result_str.c_str(), result_len);
return 0;
}
运行结果
两个函数，一个求长度，一个求结果
篇幅较长，建议仔细理解