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

题目大意：
给个字符串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是否是回文。

代码：
[cpp]
#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; 
}