单位建设网站需要的材料,本机iis网站,全国知名网站排名,可以做海报的网站计算字符串内的最大回文子串#xff0c;常用的暴力扩散在应对长度为偶数的回文时会遇到一些问题。 Manacher基础#xff1a;对字符串进行填充#xff0c;在字符串开头结尾以及字符间填充‘#’#xff0c;以来应对偶数回文时的问题。#xff08;这是采用暴力扩再除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-i1
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;vectorint arr(str.size() , 0);for(int i 0 ; istr.size() ; i){arr[i] Ri?min(arr[2*C-i] , R-i):1;while(iarr[i]str.size() i-arr[i]-1){if(str[iarr[i]]str[i-arr[i]])arr[i];else break;}num max(num , arr[i]);if(numarr[i])temp str.substr(i-arr[i]1 , 2*arr[i]-1);}string res ;for(auto ch : temp){if(ch!#){res ch;}}return res;}
}; 滑动窗口
使用双指针来代表一个当前窗口左指针和右指针都只能往右滑动L不能超过R 1. 准备一个双端队列存储数组下标保证队列内数据单调排序
2. 右指针右滑队列为空直接进如果不为空判断是否小于队列尾部数据直接进如果大于等于弹出队列数据直到满足队列为空或小于条件
3. 左指针右滑判断队列头部数据对应下标是不是左指针左方的下标如果是从头部弹出 单调栈
知道每一个数左边最近的大数和右边最近的大数是谁无重复数并且时间复杂度O(N)
1. 栈空直接进如果不为空判断该数是否小于栈顶元素若小于直接进否则弹出栈内数据生成该数的左右信息弹出的数左信息为压着的右信息为当前数满足条件后近栈
2. 遍历结束进入清算阶段依次出栈并生成信息 如果有重复数据的话用链表来存放即可哈希表链表下标数据值
