鏈接：

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

題目大意：

給個(gè)字符串S，要把S分成兩段T1,T2，每個(gè)字母都有一個(gè)對(duì)應(yīng)的價(jià)值，如果T1，T2是回文串（從左往右或者從右往左讀，都一樣），那么他們就會(huì)有一個(gè)價(jià)值，這個(gè)價(jià)值是這個(gè)串的所有字母價(jià)值之和，如果不是回文串，那么這串價(jià)值就為0。問(wèn)最多能獲得多少價(jià)值？

分析與總結(jié)：

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

S：acacac

T：cacaca

如果要求S的前綴回文，只需要用拓展KMP算法讓S去匹配T，求出所有T的后綴T【i】與S前綴的公共串長(zhǎng)度，保存在extend數(shù)組中，得到：0， 5， 0， 3， 0， 1

其中extend中的位置1,3,5是有公共串的，并且匹配的長(zhǎng)度滿足extend[i] + i == len, len=|S|.

并且S這幾個(gè)長(zhǎng)度的前綴都是回文串！

所以，對(duì)于我們只需要枚舉掃描一遍extend數(shù)組，掃描到的當(dāng)前位置之前為前半部分T1， 然后用根據(jù)extend數(shù)組可以判斷T1是否是回文。那后半部分T2呢？ 剛才是用S去匹配T， 如果要求后綴，只需要用T去匹配S，再得到一個(gè)數(shù)組extend2即可，根據(jù)這個(gè)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;
}
  

—— 生命的意義，在于賦予它意義士。

原創(chuàng) http://blog.csdn.net/shuangde800 ， By D_Double (轉(zhuǎn)載請(qǐng)標(biāo)明)

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