Best Reward HDU 3613（回文子串Manacher）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意：有一个串（全部由小写字母组成），现在要把它分成两部分，如果分开后的部分是回文串就计算出来它的价值总和，如果不是回文的那么价值就是0，最多能得到的最大价值。

分析：首先的明白这个最大价值有可能是负数，比如下面：

-1 -1 -1.....

aaa

这样的情况不管怎么分，分出来的串都是回文串，所以得到的最大价值是 -3。

求回文串的算法使用的是Manacher算法，线性的复杂度。

代码如下：

================================================================================================================

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

const int MAXN = 1e6+;

const int MAXM = ;

const int oo = 1e9+;

char str[MAXN];

int p[MAXN], val[], sum[MAXN];

bool Left[MAXN], Right[MAXN];

/**

str[]   先存原字符串，后存扩展后的字符串

p[]     p[i] 表示以i为中心的回文串有多长（只记录一边的长度）、

sum[]   sum[i]表示前i个字符的总价值和

Left[]  Left[i] 表示前缀长度为 i 的串是否是回文串

Right[] Right[i]  表示后缀长度为 i 的串是否是回文串

**/

void Manacher(char str[], int N)

{

    int i, id=;

    for(i=; i<N; i++)

    {

        if(p[id]+id > i)

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

        else p[i] = ;

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

            p[i]++;

        if(p[id]+id < p[i]+i)

            id = i;

        if(p[i] == i)

            Left[p[i]-] = true;

        if(p[i]+i- == N)

            Right[p[i]-] = true;

    }

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int i;

        memset(Left, false, sizeof(Left));

        memset(Right, false, sizeof(Right));

        memset(p, false, sizeof(p));

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

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

        scanf("%s", str);

        int len = strlen(str);

        for(i=; i<=len; i++)

            sum[i] = sum[i-]+val[str[i-]-'a'];

        for(i=len; i>=; i--)

        {

            str[i+i+] = str[i];

            str[i+i+] = '#';

        }

        str[] = '$';

        Manacher(str, len+len+);

        int ans = -oo;

        for(i=; i<len; i++)

        {

            int temp = ;

            if(Left[i] == true)

                temp += sum[i];

            if(Right[len-i] == true)

                temp += sum[len]-sum[i];

            ans = max(ans, temp);

        }

        printf("%d\n", ans);

    }

    return ;

}