HDU 3613 Best Reward(拓展KMP求前缀回文串)

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3613

题目大意：

给个字符串S，要把S分成两段T1,T2，每个字母都有一个对应的价值，如果T1，T2是回文串（从左往右或者从右往左读，都一样），那么他们就会有一个价值，这个价值是这个串的所有字母价值之和，如果不是回文串，那么这串价值就为0。问最多能获得多少价值？

分析与总结：

观察字符串S，以及由S逆序得到的字符串T：

S：acacac

T：cacaca

如果要求S的前缀回文，只需要用拓展KMP算法让S去匹配T，求出所有T的后缀T【i】与S前缀的公共串长度，保存在extend数组中，得到：0， 5， 0， 3， 0， 1

其中extend中的位置1,3,5是有公共串的，并且匹配的长度满足extend[i] + i == len, len=|S|.

并且S这几个长度的前缀都是回文串！

所以，对于我们只需要枚举扫描一遍extend数组，扫描到的当前位置之前为前半部分T1， 然后用根据extend数组可以判断T1是否是回文。那后半部分T2呢？ 刚才是用S去匹配T， 如果要求后缀，只需要用T去匹配S，再得到一个数组extend2即可，根据这个extend2判断后半部分T2是否是回文。

代码：

    #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 500005;
char S[MAXN];
char T[MAXN];
int  f[MAXN];
int  extend1[MAXN];
int  extend2[MAXN];
int  val[30];
int  sum[MAXN];

void revcpy(char* s,char* t,int len){
    memset(t, 0, sizeof(t));
    for(int i=0, k=len-1; i<len; ++i,--k)
        t[i] = s[k];
}
void getNext(char* T,int* next){
    int len=strlen(T), a=0;
    next[0]=len;
    while(a<len-1 && T[a]==T[a+1]) ++a;
    next[1]=a;
    a=1;
    for(int k=2; k<len; ++k){
        int p=a+next[a]-1, L=next[k-a];
        if(k+L-1>=p){
            int j=max(p-k+1,0);
            while(k+j<len && T[k+j]==T[j])++j;
            next[k]=j;
            a=k;
        }
        else
            next[k]=L;
   }
}

void EKMP(char* S,char* T,int* next, int* extend){  
    getNext(T,next);  
    int slen=strlen(S), tlen=strlen(T), a=0;  
    int minlen=min(slen,tlen);  
    while(a<minlen && S[a]==T[a])++a;  
    extend[0] = a;  
    a=0;  
    for(int k=1; k<slen; ++k){  
        int p=a+extend[a]-1, L=next[k-a];  
        if(k-1+L >= p){  
            int j=max(p-k+1,0);  
            while(k+j<slen && j<tlen && S[k+j]==T[j]) ++j;  
            extend[k] = j;  
            a=k;  
        }  
        else  
            extend[k] = L;  
    }  
}   

int main(){
    int nCase;
    scanf("%d",&nCase);
    while(nCase--){
        for(int i=0; i<26; ++i)
            scanf("%d",&val[i]);
        scanf("%s",S);
        memset(sum, 0, sizeof(sum));
        for(int i=0; S[i]; ++i){
            sum[i+1] = val[S[i]-'a']+sum[i];
        }
        int len=strlen(S);
        revcpy(S,T,strlen(S));
        EKMP(S,T,f,extend2);
        EKMP(T,S,f,extend1);

        int maxx=-1000000000;

        for(int i=0; i<len; ++i){
            if(i && extend1[i]+i==len){ //如果半部分是回文
                int pos=extend1[i];
                int tmp=sum[pos];
                if(extend2[pos]+pos==len){  // 看后半部分是否也是回文
                    tmp += sum[len]-sum[pos];
                }
                if(tmp > maxx)
                    maxx=tmp;
            }
            else{ //如果前半部分不是回文，看后半不部分
                int pos=i+1,tmp=0;
                if(extend2[pos]+pos==len){
                    tmp += sum[len]-sum[pos];
                }
                if(tmp > maxx)
                    maxx=tmp;
            }
        }
        printf("%d\n",maxx);
    }
    return 0;
}
  

—— 生命的意义，在于赋予它意义士。

原创 http://blog.csdn.net/shuangde800 ， By D_Double (转载请标明)

HDU 3613 Best Reward(拓展KMP求前缀回文串)