中心扩散算法--最长回文子串

      这篇看一下中心扩散算法。

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2:输入: "cbbd" 输出: "bb"

  代码：

  

#include<iostream> #include<string> #include<vector> #include<map> #include<utility>using namespace std; //最长回文子串//中心扩散算法 class Solution { public:pair<int, int> expandAroundCenter(const string& s, int left, int right) {while (left >= 0 && right < s.size() && s[left] == s[right]) {--left;++right;}return {left + 1, right - 1};}string longestPalindrome(string s) {int start = 0, end = 0;for (int i = 0; i < s.size(); ++i) {//1个边界条件auto [left1, right1] = expandAroundCenter(s, i, i);//2个相等字母的边界条件auto [left2, right2] = expandAroundCenter(s, i, i + 1);cout << "left1=" << left1 << "," << "right1=" << right1 << endl;cout << "left2=" << left1 << "," << "right2=" << right1 << endl;//判断新的回文子串是否比前面的长if (right1 - left1 > end - start) {start = left1;end = right1;}if (right2 - left2 > end - start) {start = left2;end = right2;}cout << "-------------------" << endl;}cout << "start=" << start << "end=" << end << endl;return s.substr(start, end - start + 1);} };int main(){string str = "babad";Solution s;auto ret = s.longestPalindrome(str);cout << ret << endl;return 0; }

  运行：

left1=0,right1=0
left2=1,right2=0
-------------------
left1=0,right1=2
left2=2,right2=1
-------------------
left1=1,right1=3
left2=3,right2=2
-------------------
left1=3,right1=3
left2=4,right2=3
-------------------
left1=4,right1=4
left2=5,right2=4
-------------------
start=0end=2
bab

这个分为1位扩散和2位扩散

 

代码地址：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

总结

以上是生活随笔为你收集整理的中心扩散算法--最长回文子串的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。