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的长度，此时仍需向左右两边扩散求最长回文串。

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;
}