给定一个字符串，$O(n)$ 时间内找出以每一个字符为回文中心时的最大回文长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> manacher(string s)
{
    string t;
    for(auto c:s)
    {
        t+=string("#")+c;
    }
    t+=string("#");
    int n=t.length();
    vector<int>p(n+2);
    t="$"+t+"%";
    
    int l=1,r=1;
    for(int i=1;i<=n;i++)
    {
        p[i]=max((int)0,min(r-i,p[l+r-i]));
        
        while(t[i+p[i]+1]==t[i-p[i]-1])p[i]++;
        if(i+p[i]>r)
        {
            r=i+p[i];
            l=i-p[i];
        }
    }
    return vector<int>(begin(p)+2,end(p)-2);
}