manacher

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
char s[11000005];
int n,d1[11000005],d2[11000005];
inline void manacher()
{
    n=strlen(s+1);
    for(int i=1,l=1,r=0;i<=n;++i)
    {
        int k=(i>r)?1:min(d1[l+r-i],r-i+1);
        while((0<=i-k)&&(i+k<=n)&&(s[i+k]==s[i-k]))k++;
        d1[i]=k--;
        if(i+k>r)r=i+k,l=i-k;
    }
    for(int i=1,l=1,r=0;i<=n;++i)
    {
        int k=(i>r)?0:min(d2[l+r-i+1],r-i+1);
        while((0<i-k)&&(i+k<=n)&&(s[i-k-1]==s[i+k]))k++;
        d2[i]=k--;
        if(i+k>r)r=i+k,l=i-k-1;
    }
}