算法笔记（十二）—— Manacher算法（回文子串）

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

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.  遍历结束，进入清算阶段，依次出栈并生成信息

如果有重复数据的话，用链表来存放即可，哈希表<链表<下标>，数据值>