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; 
}