当前位置：首页 > news >正文

吉林省住房和城乡建设部网站家装公司建设网站

news 2025/11/6 8:53:08

吉林省住房和城乡建设部网站,家装公司建设网站,帮忙注册公司,网站设计培训课程计算字符串内的最大回文子串，常用的暴力扩散在应对长度为偶数的回文时会遇到一些问题。 Manacher基础：对字符串进行填充，在字符串开头结尾以及字符间填充‘#’，以来应对偶数回文时的问题。（这是采用暴力扩再除2&#x…

计算字符串内的最大回文子串，常用的暴力扩散在应对长度为偶数的回文时会遇到一些问题。

Manacher基础：对字符串进行填充，在字符串开头结尾以及字符间填充‘#’，以来应对偶数回文时的问题。（这是采用暴力扩再除2，可以得到正确的结果）

填充的字符不一定需要添加字符串内没有出现的字符

时间复杂度：O(N^2)

Manacher算法 - O(N^2)

概念：

回文直径：每个字符暴力扩的最大回文子串长度

回文半径：回文直径的一半

回文半径数组：将每个字符对应的回文半径信息存储起来

之前所扩的所有位置中所达到的最右边界 init R = -1

C：取最远边界时，中心点在哪

情况处理：

1. 当前来到的点不在右边界内：暴力扩

2. 当前点在R内，R关于C的对称点L，当前点关于C的对称点i'

2.1 i'的回文区域彻底在[L R]的内部，则当前点的回文半径等于i'的回文半径

2.2 i'的回文区域有一部分在[L R]外，则i的回文半径等于R-i+1

2.3 i'的回文区域压在了[L R]上，i的回文半径从R开始暴力扩计算即可

// Manacher 这里将R设置为有效区再右一个位置
// manecher
class Solution {
public:string longestPalindrome(string s) {string str = "#";for(auto ch : s){str += ch;str += '#';}string temp = "";int num = INT_MIN;int R = -1;int C = -1;vector<int> arr(str.size() , 0);for(int i = 0 ; i<str.size() ; i++){arr[i] = R>i?min(arr[2*C-i] , R-i):1;while(i+arr[i]<str.size() && i-arr[i]>-1){if(str[i+arr[i]]==str[i-arr[i]])++arr[i];else break;}num = max(num , arr[i]);if(num==arr[i])temp = str.substr(i-arr[i]+1 , 2*arr[i]-1);}string res = "";for(auto ch : temp){if(ch!='#'){res += ch;}}return res;}
};