字符串---Manacher

求最长回文子串

求一个串中的回文子串，首先将字符串处理成奇数个。
如"abbc"处理成Ma = "$ a # b # b # c #"
然后求出以每个字符为中心的回文半径Mp
最大的那个回文半径就对应着最长的回文子串
代码中id指以这个点为中心半径可以达到右边最远，达到的位置是mx
2*id-i 指的是i关于 id的对称位置i",(i肯定在id的右边,因为是从左往右遍历处理)
设当前位置为i,要计算Mp[i]:
如果，mx>i(图1,2)，即id处的回文半径能够覆盖当前位置，那么i的对称位置i"一定也在以id为中心的回文串中，并且 i"位于id左边，已经处理过，Mp[2*id-i]就是i"的回文半径。
这时候计算i的回文半径还分两种情况。mx-i > Mp[2*id-i]和mx-i < Mp[2*id-i]，分别对应图1,2。Mp[i]的值选取两者中小的那一个。因为图中只有同时被红色和绿色覆盖的，才关于i对称，其他的未知。

image
如果，mx <= i(图3)，那么i的回文半径只能通过一次次比较求得。
细节见代码

namespace Manacher{
    const int MAXN = 100;//字符串最大长度
    char Ma[MAXN*2];//处理后的字符串
    int Mp[MAXN*2];//每个位置的回文半径,max(Mp[i])-1就是最长回文长度
    int Manacher(const char s[], int len){
        int l = 0, ret = 0;
        Ma[l++] = '$';
        Ma[l++] = '#';
        for(int i = 0; i<len; i++){
            Ma[l++] = s[i];
            Ma[l++] = '#';
        }
        Ma[l] = 0;
        int mx = 0, id = 0; //从id处回文半径可以达到mx处
        for(int i = 0; i < l; i++){
            Mp[i] = mx > i ? min(Mp[2*id-i], mx - i) : 1;
            while(Ma[i + Mp[i]] == Ma[i - Mp[i]]) Mp[i]++;
            ret = max(Mp[i]-1,ret);
            if(i + Mp[i] > mx){
                mx = i + Mp[i];
                id = i;
            }
        }
        return ret;
    }
}

例题

POJ3974 裸题