Manacher算法lyh's blog

        Manacher算法是一种求字符串中最长回文子串的高效算法。

        回文字符串，就是将字符串倒置后与原字符串完全相同的字符串，如a、aba、abcba等等。
        传统的求回文子串的方法是$O(n^2)$的，那样的算法比较低效。Mnacher可以在线性时间内求出最长回文子串，这个算法充分利用了回文的性质。
        注意到回文子串有奇数个和偶数个之分，这为我们的算法造成了困难，因此在算法进行之前，先对字符串进行一步预处理。预处理的方法就是在每两个相邻字符之间和字符串首尾加一个新的字符。注意这个字符不能在原字符串中出现过，这里我们选择’%’为例。对于字符串abcd，预处理后得到%a%b%c%d%。
        这样做的好处是，无论奇数个还是偶数个数目的回文子串，都可以找到一个对称中心。也就是说，预处理后的字符串的回文子串都是以某个字符为对称中心轴对称的，这样我们求出每一个字符的最长对称长度即可。
        用p[i]表示第i个字符的最长对称长度（对称长度是指这个字符向右或者向左最大能延伸的距离，含该字符本身）。并且容易知道实际的回文串长度为p[i]-1。
        若下标从0开始，则初始化p[0]=1，接下来就是Manacher算法核心步骤。
        从小到大枚举下标i，这个过程中用一个变量r表示目前回文串最右延伸位置的下一个位置，pos记录这个最右延伸位置回文串所对应的对称中心在字符串中的下标，然后分情况讨论。r初始化为1，pos初始化为0。
        如果i < r。找到i关于pos的对称点2pos-i，易知2pos-i这个字符位于pos对应的回文串中，因此有两段字符串相同：$[2pos-r+1,2pos-i]=[i,r-1]$，当然也有$[2pos-i,pos]=[pos,i]$。这说明i的临近部分与2pos-i的临近部分是相同的，若$p[2pos-i]≤r-i$，则p[i]至少为p[2pos-i]，这是一个显然的结论；如果$p[2pos-i] >r-i$，p[i]应至少为r-i，这是因为我们并不清楚r右侧的情况，只能得到r左侧回文串的长度。综合来看，有$p[i]=\min(p[2pos-i],r-i)$。
        上面只是得到了“至少”的长度，还需扩展，下面用for循环延伸这个长度。对于i≥r的情况直接令p[i]=1，然后for循环延伸。最后要注意更新r和pos。

int pos = 0, r = 1;
p[0] = 1;
for (int i = 1; i < l; i++) {
    if (i < r)p[i] = min(p[2 * pos - i], r - i);
    else p[i] = 1;
    for (; i - p[i] >= 0 && i + p[i] < l && op1[i - p[i]] == op1[i + p[i]]; ++p[i]);
    if (p[i] + i > r)r = p[i] + i, pos = i;
}

最后统计答案即可，完整代码，洛谷模板题：

#include<bits/stdc++.h>

using namespace std;
char op1[(11000000 << 1) + 5], op2[11000000];
int p[(11000000 << 1) + 5];
int l;

int main() {
    ios::sync_with_stdio(false);
    cin >> op2;
    l = strlen(op2);
    for (int j = 0, i = 0, k = 0; j < l; k ^= 1) {
        if (!k)op1[i++] = '%';
        else op1[i++] = op2[j++];
    }
    op1[l++] = '%', l = strlen(op1);
    int pos = 0, r = 1;
    p[0] = 1;
    for (int i = 1; i < l; i++) {
        if (i < r)p[i] = min(p[2 * pos - i], r - i);
        else p[i] = 1;
        for (; i - p[i] >= 0 && i + p[i] < l && op1[i - p[i]] == op1[i + p[i]]; ++p[i]);
        if (p[i] + i > r)r = p[i] + i, pos = i;
    }
    int ans = -1;
    for (int i = 0; i < l; i++)ans = max(ans, p[i] - 1);
    cout << ans;
    return 0;
}

Manacher算法的一些特点

Manacher算法很好用，但是现在已经不可能裸地考察Manacher最基本应用的问题了，都需要有一些变化或者将Manacher与SAM、SA配合着来使用，这样就需要我们知道Manacher算法的一些特点。

Manacher算法可以在$O(n)$的量级下遍历字符串的所有回文子串，这些回文子串并不保证互不相同。
Manacher算法得到的回文串一定是以我们添加的特殊字符开始和结束。

不要小看这两个结论，它们可能是与SAM、SA结合时的重要算法正确性依据。其余的特点待以后补充。

Manacher算法应用：判定二叉树的对称性

        如果将一棵二叉树的所有结点左右儿子翻转，可以得到这棵二叉树的镜像对称树，如果两棵树结构相同，则称二叉树满足对称性。现在对于有根二叉树，需要找到上面所有对称子树，传统的判定对称性算法需要$O(n^2)$，应用Manacher算法能直接降至$O(n)$。
        方法是先应用一遍DFS将所有点的子结点数目统计出来，再来一遍中序遍历，得到遍历序列，序列元素是结点的子结点数目。易知一棵对称二叉树与中序遍历序列中的一个回文串对应，在其上应用Manacher算法即可。
        来一道水题：洛谷P5018，这里不仅需要判结构对称还需要权值对称，后者本质相同，总时间复杂度$O(n)$。

#include<bits/stdc++.h>

#define N 10000005
using namespace std;
int ch[N][2], v[N], n, num[N], check[N];
int rk[N << 1], tot, rk2[N << 1], p1[N << 1], p2[N << 1], to[N];

inline int read() {
    char e = getchar();
    int s = 0, g = 0;
    while (e < '-')e = getchar();
    if (e == '-')g = 1, e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return g ? -s : s;
}

void preDFS(int x) {
    if (x == 0)return;
    preDFS(ch[x][0]), preDFS(ch[x][1]);
    if (num[ch[x][0]] == num[ch[x][1]])check[x] = num[ch[x][0]];
    num[x] = num[ch[x][0]] + num[ch[x][1]] + 1;
}

void DFS(int x) {
    if (x == 0)return;
    DFS(ch[x][0]);
    rk[++tot] = num[x], rk2[tot] = v[x], to[tot] = x;
    rk[++tot] = -1, rk2[tot] = -1;
    DFS(ch[x][1]);
}

int main() {
    //freopen("text.in", "r", stdin);
    n = read();
    for (int i = 1; i <= n; i++)v[i] = read();
    for (int i = 1; i <= n; i++) {
        int x = read(), y = read();
        if (x != -1)ch[i][0] = x;
        if (y != -1)ch[i][1] = y;
        check[i] = -1;
    }
    preDFS(1), rk[++tot] = -1, rk2[tot] = -1, DFS(1);
    int pos = 1, r = 2, ans = 0;
    p1[1] = 1;
    for (int i = 2; i <= tot; i++) {//结构Manacher
        if (i < r)p1[i] = min(p1[2 * pos - i], r - i);
        else p1[i] = 1;
        for (; i > p1[i] && i + p1[i] <= tot && rk[i - p1[i]] == rk[i + p1[i]]; ++p1[i]);
        if (p1[i] + i > r)r = p1[i] + i, pos = i;
    }
    pos = 1, r = 2, p2[1] = 1;
    for (int i = 2; i <= tot; i++) {//权值Manacher
        if (i < r)p2[i] = min(p2[2 * pos - i], r - i);
        else p2[i] = 1;
        for (; i > p2[i] && i + p2[i] <= tot && rk2[i - p2[i]] == rk2[i + p2[i]]; ++p2[i]);
        if (p2[i] + i > r)r = p2[i] + i, pos = i;
    }
    for (int i = 1; i <= tot; i++) {
        if (rk[i] != -1 && check[to[i]] != -1) {
            if (check[to[i]] <= ((p1[i] - 2) >> 1) && check[to[i]] <= ((p2[i] - 2) >> 1))
                ans = max(ans, num[to[i]]);
        }
    }
    cout << ans;
    return 0;
}