# Manacher

title: Manacher mathjax: true data: 2020-03-24 19:20:31 updated: tags: -最长回文字串 categories:

## -算法

manacher算法是用来求最长回文字串的，最长回文字串有一种经典求法：就是在源字符串中的每个字符前添加一个额外字符(这个额外字符并要求一定是源字符串中没有出现过的字符)，添加完后，依次求每一个位置上的最大回文字串，然后除以2，就是源字符串对应位置的最长回文字串。例如：`122131221`改为`#1#2#2###1#2#2#1#`.。 那么如果不添加求呢？不添加的话，会错过长度为偶数的最长回文字串。

manacher算法中有以下几个概念(适用范围：添加额外字符后字符串)，以`#1#2#2#1#3#1#2#2#1#`为例：

* 回文直径：一个位置上的最大回文子串
* 回文半径：一个位置上的最大回文字串的一半，**要包含中点**，比如字串`#1#2#2#1#`,左`2`位置的回文半径为2，包括`2#`,完整回文串为`#2#`,回文直径为3
* 最大右边界：一个位置上的最大回文字串最右边界位置：比如`#1#2#2#1#`,左`2`的最大右边界为4，如果有新位置产生了新的最大右边界，那么需要更新
* 取得最大右边界时的中心点：仍拿上述字串为例：`#1#2#2#1#`，左`2`的中心点位置为3。

manacher算法求最大回文字串有两种大分支，第二个大分支有三种小情况：

* 第一种情况：当前i位置大于最大右边界R，这时就硬求最长回文字串
* 第二种情况：当前i位置小于最大有边界R，这是有三种情况：
  * `i`位置的对称`i'`的最长回文字串完全在最大左边界`L`的右侧，即完全被包含，这时`i'`的最长回文串半径就是`i`位置的最长回文串半径,假设`i'`的最长回文串前一字符和下一字符为`x`和`y`，x不等于y，所以`i`位置的最长回文串的上一和下一字符为`m`和`n`，m和n肯定不是相等的，因为m等于y，n等于x(因为这两个子串都被包含于\[L,R]中)
  * `i`位置的对称`i'`的最长回文串跨过了最大左边界`L`，这时`i`位置的最长回文串长度就是右边界`R`到`i`的长度。因为假设L的上一字符为`x`,R的下一字符为`y`，x和y肯定不是相等的，因为x和y都在最大的回文串\[L,R]外，说明i为位置的最大回文串半径就是`R-i`的长度
  * `i`位置的对称`i'`的最长回文串恰好在最大左边界`L`，这是`i`位置的最长回文串半径不知道，只能知道最小回文串是右边界`R`到`i`的长度，此时仍需向左右两边扩散求最长回文串。

```cpp
int MaxLcpsLength(const string& s){
    if(s.empty()){
        return 0;
    }
    string str=GetManacherString(s);
    int C{-1};//最大回文半径的中点
    int R{-1};//最大右边界的下一位置，方便写
    //最长回文半径数组，保存了每个位置的最长回文半径
    vector<int> pArr(str.size());
    int Max=INT_MIN;
    //求每个位置的最长回文子串
    for(int i=0;i<str.size();++i){
        //先求出最小的回文半径,三种情况放一块了，2*C-i是对称的i'位置，因为对称点距离左右两个边界偏移是相同的，R-i是i位置距离R的最大回文半径，二者取小
       pArr[i]=R>i?min(pArr[2*C-i],R-i):1;
       //pArr[i]是i位置的最小回文半径，i+pArr[i]就是下一个待比对的字符
        while(i+pArr[i]<str.size() &&i-pArr[i]>-1){
            //同样也是四合一
            if(str[i+pArrp[i]]==str[i-pArr[i]]){
                pArr[i]++;
            }
            else{
                break;
            }
        }
        //i+pArr[i]实际是最大右边界的下一个字符，比如i为8，pArr[i]=3;说明最大右边界实际为10，因为这里算上8，下一位置就是i+pArr[i]=11
        if(i+pArr[i]>R){
            R=i+pArr[i];
            C=i;
        }
        Max=max(pArr[i],Max);
    }
    //因为Max是包含多余字符的最长回文半径，Max-1就是源字符串的最长回文长度
    return Max-1;
}
```
