Manacher算法求回文半径

http://wenku.baidu.com/link?url=WFI8QEEfzxng9jGCmWHoKn0JBuHNfhZ-tKTDMux34CeY8UNUwLVPeY5HA3TyoKU2XegXFPifjunarW-YmXFrP_m8-3DEhBu1MHxHghHqD0O

这篇讲的比较好，准备一个模板，做题的时候用。

void manacher()

{

    int mx = , id = ;

    for (int i = ; i <= n; i++)

    {

        if (mx > i)

            p[i] = min(p[id *  - i], mx - i);

        else

            p[i] = ;

        while (a[i + p[i]] == a[i - p[i]])

            p[i]++;

        if (mx < p[i] + i)

        {

            mx = p[i] + i;

            id = i;

        }

    }

}

这个初始化的时候是从1开始的

for (int i = ; i <= n; i++)

{

            a[i *  - ] = str[i];

            a[i * ] = -;

}

其中p表示回文半径，str是原串，a表示添加字符之后的串

两个例题：

hdu5340

#include <cstdio>

#include <iostream>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = ;

char str[maxn], a[maxn<<];

int p[maxn<<], L[maxn<<], R[maxn<<];

int n;

void manacher()

{

    int mx = , id = ;

    for (int i = ; i <= n; i++)

    {

        if (mx > i)

            p[i] = min(p[id *  - i], mx - i);

        else

            p[i] = ;

        while (a[i + p[i]] == a[i - p[i]])

            p[i]++;

        if (mx < p[i] + i)

        {

            mx = p[i] + i;

            id = i;

        }

    }

}

bool solve()

{

    for (int i = ; i <= L[]; i++)

    {

        for (int j = ; j <= R[]; j++)

        {

            int l = L[i] + ;

            int r = R[j] - ;

            if (r - l <= )

                continue;

            int mid = (l + r) / ;

            if (p[mid] >= r - mid + )

                return true;

        }

    }

    return false;

}

int main()

{

    int T;

    scanf("%d", &T);

    while (T--)

    {

        scanf("%s", str + );

        n = strlen(str + );

        for (int i = ; i <= n; i++)

        {

            a[i *  - ] = str[i];

            a[i * ] = '#';

        }

        n = n *  - ;

        a[] = '$';

        a[n + ] = '@';

        manacher();

        memset(L, , sizeof(L));

        memset(R, , sizeof(R));

        for (int i = ; i <= n; i++)

        {

            int l = i - p[i] + ;

            int r = i + p[i] - ;

            if (l == )

                L[++L[]] = r;

            if (r == n)

                R[++R[]] = l;

        }

        if (solve())

            puts("Yes");

        else

            puts("No");

    }

    return ;

}

hdu5371

#include <cstdio>

#include <iostream>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = ;

int str[maxn], a[maxn<<];

int p[maxn<<];

int n;

void manacher()

{

    int mx = , id = ;

    for (int i = ; i <= n; i++)

    {

        if (mx > i)

            p[i] = min(p[id *  - i], mx - i);

        else

            p[i] = ;

        while (a[i + p[i]] == a[i - p[i]])

            p[i]++;

        if (mx < p[i] + i)

        {

            mx = p[i] + i;

            id = i;

        }

    }

}

void print()

{

    for (int i = ; i <= n; i++)

        printf("%d ", p[i]);

}

int main()

{

    int T;

    int kase = ;

    scanf("%d", &T);

    while (T--)

    {

        scanf("%d", &n);

        for (int i = ; i <= n; i++)

            scanf("%d", &str[i]);

        for (int i = ; i <= n; i++)

        {

            a[i *  - ] = str[i];

            a[i * ] = -;

        }

        int m = n;

        n = n *  - ;

        a[] = -;

        a[n + ] = -;

        manacher();

        int ans = ;

        for (int i = ; i <= n; i += )

            p[i] /= ;

        for (int i = ; i <= n; i += )

        {

            if (p[i] *  < ans)

                continue;

            for (int j = p[i]; j *  >= ans; j--)

            {

                if (p[i + j * ] >= j)

                {

                    ans = max(ans, j * );

                    break;

                }

            }

        }

        printf("Case #%d: %d\n", ++kase, ans);

    }

    return ;

}