HDU 3613 Best Reward ---- 拓展KMP

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

此题是个很好的例子，入门的最好不过。

SOL：（转自KuangBin）

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

一定要分成两部分噢，不能不分。

#include   
#include   
#include   
#include   
  
using namespace std;  
  
const int maxn = 500000 + 10;  
char str1[maxn],str2[maxn];  
int next[maxn];  
int extend1[maxn],extend2[maxn];  
int sum[maxn];  
int val[27];  
  
//s为主串，t为子串   
void ekmp(char *s,char *t,int *next,int *extend)  
{  
    int i,j,p,L;  
    int lens=strlen(s);  
    int lent=strlen(t);  
    next[0]=lent;  
    j=0;  
    while(i+j





>1;  
        //需要保证分成两部分，所以i从1到len-1  
        for(int i=1;ians)  ans=tmp;  
        }  
        printf("%d\n",ans);  
    }  
    return 0;  
}