不容易解的题10.10

5.最长回文子串

5. 最长回文子串 - 力扣（LeetCode）https://leetcode.cn/problems/longest-palindromic-substring/?envType=list&envId=ZCa7r67M给一个字符串，让我们找最长回文子串

这题不用说，回文子串那一定是连续的，第一眼看可能想到滑窗，想法是好想法，但是你如何确定窗口大小？又如何确定窗口什么情况下左窗口怎么运动，又是什么情况右窗口运动呢？为了找全子串不落下答案，那我们应该从第一个位置开始左窗口，那么什么时候左窗口右移动呢？

这实际上就只能使用双for循环来确定此时子串开始终止位置了，然后判断该字串是否回文，如果回文看长度更新答案。没错最开始我就是这样想的，也是这样实现的，但是需要右剪枝，不然容易超时。

class Solution {
public:
bool fun(string&s,int left,int right){while(left<right){if(s[left++]!=s[right--])return false;}return true;
}string longestPalindrome(string s) {if(s.size()==0)return "";string res;res+=s[0];for(int i=0;i<s.size();i++){for(int j=i+1;j<s.size();j++){bool t=fun(s,i,j);if(t){string tmp=s.substr(i,j-i+1);res=tmp.size()>res.size()?tmp:res;}if(j+1==s.size()&&res.size()==j-i+1)return res;}}return res;}
};

剪枝就是如果当前右窗口已经遍历到整个s最后一个位置且res也等于该窗口大小
则直接return因为后面不可能存在更长的回文子串了

怎么样是不是还算有一点技巧，时间消耗非常多，大概200+，而且我也是超时后才想到这个剪枝的，更好的算法我在这里介绍两个，一个是中心探测，一个是马拉车（竞赛算法）。

中心探测是马拉车算法的雏形（基础），也就是说你不会中心探测写不出来马拉车算法，但我个人觉得中心探测就十分的好用了，它可以使时间消耗变得很小了，如果不是在特殊要求时间或性能的前提下，使用中心探测可以更好的更快速的不出错的书写代码。

思路：中心探测法要求以字符串的每个字符作为中心探测的中心点，开始向两边进行试探，判断两边的元素是否对应相等，这里有一个不太容易察觉的问题

一个字符串的长度奇偶性会影响判断的结果，如果长度为奇数那非常好办，以中点左右探测不会出现问题，但如果为偶数不容易确定取拿一个为中心点，我们使用填充字符串的技术，无论给定字符串长度奇偶性如何，都用字符填充使它变成奇数长度。

然后再去比较，代码如下

class Solution {
public:
int fun(const string& s,int left,int right){while(left>=0&&right<s.size()&&s[left]==s[right]){left--,++right;}return (right-left-2)/2;
}string longestPalindrome(string s) {string ss="#";int n=0;int start=0,maxn=0;for(char i:s){ss+=i;ss+='#';}for(int i=0;i<ss.size();++i){int n=fun(ss,i,i);if(maxn<n){maxn=n;start=(i-maxn)/2;}}return s.substr(start,maxn);}
};

这里我们使用#号填充，实际你用一个字符串里肯定不会出现的字符填充就可以不一定非要#。

判断回文和更新答案这里我说一下，直接看可能看不懂。

我们由于扩大了字符串用井号，而且是相当于每个原本字符的左右两边各含有一个#（注：原版是在最后一个字符填写完之后，还要有一个#填充，这里我发现少写一个也能通过），这相当于原本的字符下标扩大1倍，我们使用函数fun来返回当前以该字符为中心回文子串长度，返回结果时候需要-2这是因为left--，right++后我们发现的不回文，返回答案，所以实际应该取的答案比这小2，再就是/2，为什么除2，因为我们的得到的长度是扩大1倍下标的长度/2才是源字符串回文长度

解释完了这个解释里面的更新数据，maxn更新一目了然，然后是start这个是代表源字符串从哪个字符起取回文子串，是当前下标减去回文半径，因为是中心探测法，寻找的回文串，所以当前下标代表的是回文串中心而不是起始位置，所以是减法，然后这里的/2是因为#填充下标扩大1倍，所以/2。然后最后以start为开始，截取长度为maxn。

manacher算法：

class Solution {
public:string longestPalindrome(string s) {string tmp="#";for(char c:s){tmp+=c;tmp+='#';}tmp+='#';vector<int>arr(tmp.size(),0);int start=0,max=0,right=0,center=0;for(int i=0;i<tmp.size();++i){if(i<=right){int minarmlen=min(right-i,arr[2*center-i]);arr[i]=fun(tmp,i-minarmlen,i+minarmlen);}else arr[i]=fun(tmp,i,i);if(arr[i]>max){max=arr[i];start=(i-max)/2;           }if(i+arr[i]>right){center=i;right=i+arr[i];}}return s.substr(start,max);}
private:int fun(string&s,int left,int right){while(left>=0&&right<s.size()&&s[left]==s[right]){--left,++right;}return (right-left-2)/2;}
};

根据代码看讲解：

优化思路：使用一个数组来记录每个位置的以该位置为中心回文子串的最大长度
由于回文串的对称性我们可以找到以center为中心对称的那个位置
而center是随着i不断增大，且只会出现在i的左侧或和i相等
所以当前i的对称位置一定存在，我们根据镜像的那个i位置去查表，即可得知它可以向外扩张几个字符（取决于镜像位置为中心的回文串有多长）
什么时候可以依赖于查表确定跳过几个字符什么时候不可以？
跳过字符的原因是对称位置由于记录了以它为中心最长字串长度，所以遍历到i时如果可以以center为中心找到对称位置，且此时i在以center为中心的最远半径内，即可完成跳转。
即i<=right，我们取i+镜像表最长回文长度与right-i长度取最小，来完成此时的跳跃

跳跃是什么意思？就是left往前越过right往后越过一些字符，这些字符必定回文，不需要再做判断
如果i>center则不能跳跃，因为此时已经不在可预测范围内，center为中心的最长可预测范围就到right，因为最长回文子串以center中心最长到right
center如何确定？
我们往后遍历i在某时出现最长回文子串长度大于当前存储的长度时，把center移到i位置，且以该长度确定right即，当前right最远达哪里。

该思路是我自己总结较为简短的主要注意点，如果不明白可以看看更为完全的解析，我这里只把我认为最重要的几点讲明理解。

 这种思路就是用到回文镜像对称，以已知范围去减少判断回文次数，其他的代码实现就是中心探测法，练多了就明白了。

---

本期文章只有一道题，因为我发现更新三四道详解的题目会使得篇幅过长，阅读量过低，我试试只更新一道题会不会有所改变。

都看到这里了如果对您有用的话别忘了一键三连哦，如果是互粉回访我也会做的！

大家有什么想看的题解，或者想看的算法专栏、数据结构专栏，可以去看看往期的文章，有想看的新题目或者专栏也可以评论区写出来，讨论一番，本账号将持续更新。
期待您的关注