镇江市建设工程招投标网站办公室设计报价
计算字符串内的最大回文子串，常用的暴力扩散在应对长度为偶数的回文时会遇到一些问题。
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;}
};滑动窗口
使用双指针来代表一个当前窗口，左指针和右指针都只能往右滑动（L不能超过R）
1. 准备一个双端队列，存储数组下标，保证队列内数据单调排序
2. 右指针右滑，队列为空直接进，如果不为空，判断是否小于队列尾部数据，直接进；如果大于等于，弹出队列数据，直到满足队列为空或小于条件
3. 左指针右滑，判断队列头部数据对应下标是不是左指针左方的下标，如果是，从头部弹出
单调栈
知道每一个数左边最近的大数和右边最近的大数是谁（无重复数），并且时间复杂度O(N)
1. 栈空直接进，如果不为空判断该数是否小于栈顶元素，若小于，直接进；否则弹出栈内数据，生成该数的左右信息，弹出的数左信息为压着的，右信息为当前数，满足条件后近栈
2. 遍历结束，进入清算阶段，依次出栈并生成信息
如果有重复数据的话，用链表来存放即可，哈希表<链表<下标>，数据值>