一 今天唠唠嗑
首先感谢大家的关注,以及仔细地阅读
后台有小伙伴私信说,希望增加一些栏目。这些建议我都会认真听取,等我闲下来的时候,一定把公众号功能丰富一些,比如自动回复,增加别的栏目什么的~
什么,你问我什么时候闲下来
然后今天也是初级字符串算法题的最后一篇了,难题和链表一样,所有模块算法题都过完一遍,再上难题~
前两天和朋友聊天,他们公司之前面了一位北航的实习生,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;
}
运行结果
两个函数,一个求长度,一个求结果
篇幅较长,建议仔细理解