manacher ——学习

回文串

形如aaa,aa，aba之类的就是回文串，字符串关于某个位置中心对称。反之，abcd不为回文串
对于字符串str,现有个O(n)范围求出以每个位置为中心的最长回文半径——manacher

manacher

正常的求每个位置的最长回文半径，我们用暴力，复杂度是O( $n^2$n2),但是我们发现，在前面求出的半径可以拿来使用求后面的半径，从而减少一定时间。
先贴个代码，图后补

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 22000000 + 5;
int p[N];
int manacher(string s)
{
    string t = "$#";
    for(int i = 0; s[i]; i ++)
    {
        t += s[i];
        t += "#";
    }
    int len = t.length();
    int id = 0, mx = 0, mx_len = 0;
    for(int i = 1; i < len; i ++)
    {
        p[i] = i < mx ? min(mx - i, p[2 * id - i]) : 1;
        while(t[i + p[i]] == t[i - p[i]])
            p[i] ++;
        if(i + p[i] > mx)
        {
            mx = i + p[i];
            id = i;
        }
        mx_len = max(p[i], mx_len);
    }
    return mx_len;
}
int main()
{
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    cout << manacher(s) - 1 << endl;
}