题目大意：给出一个字符串，找出长度最长的回文子串，若有多个，找出字典序最小的。
用d[i][j]表示第i个字符到第j个字符的最长回文子串的长度。用b[i][j]表示第i个字符之后最近的一个值为j+’a’的字符的位置，用c[i][j]表示第i个字符之前最近的一个值为j+’a’的字符的位置。a[i]表示第i个字符，n表示字符串长度。
容易递推计算出d数组：
d[i][j]=d[i+1][j-1]+1(a[i]==a[j])
d[i][j]=max { d[i+1][j],d[i][j-1] }(a[i]!=a[j])
关键在于寻找最小字典序，首先令lef=1,rig=n，不断收缩lef和rig的两个值来寻找。
若a[lef]==a[rig]则取这个字符，lef++,rig–。a[lef]加入到答案集。
若a[lef]!=a[rig]，则原则是，判断是否用a[lef]或a[rig]，
如果用a[lef]，，那么寻找a[rig]往左的第一个和a[lef]相等的字符（就是之前计算的b[rig][a[lef]-‘a’]），在这之间的字符都是没用的，这种情况下当前最长回文子串长度将会变成d[lef][b[rig][a[lef]-’a’]]，同理如果用a[rig]，那么当前最长回文子串长度将会变成d[c[lef][a[rig]-‘a’]][rig]。
令p= d[lef][b[rig][a[lef]-’a’]]，q= d[c[lef][a[rig]-‘a’]][rig]，uu=d[lef][rig]。
如果p<uu && q<uu则a[lef]和a[rig]都不能用，lef++,rig–，
如果p<uu && q==uu，那么不可能用a[lef]，lef++，
如果p==uu && q<uu，同理不可能用a[rig]，rig–，
如果p==uu && q==uu，那么肯定不会用a[lef]或a[rig]中字典序较大的那一个。从而决定lef++还是rig–。
#include<stdio.h>#include<stdlib.h>#include<string.h>char a[1100];int b[1010][30];int c[1010][30];int d[1010][1010];char ans[1010];int main(void){int i,j,p,q,n,uu,top,lef,rig;while(gets(a+1)!=NULL){n=strlen(a+1);for(i=1;i<=n;i++){for(j=0;j<26;j++){c[i][j]=c[i-1][j];}c[i][a[i]-'a']=i;}for(i=n;i>=1;i–){for(j=0;j<26;j++){b[i][j]=b[i+1][j];}b[i][a[i]-'a']=i;}for(j=1;j<=n;j++){d[j][j]=1;}for(i=1;i<n;i++){for(j=1;j<=n-i;j++){if(a[j]==a[j+i]){d[j][j+i]=d[j+1][j+i-1]+2;}else{if(d[j][j+i-1]>d[j+1][j+i]){d[j][j+i]=d[j][j+i-1];}else{d[j][j+i]=d[j+1][j+i];}}}}lef=1;rig=n;top=0;while(rig>lef){if(a[lef]==a[rig]){top++;ans[top]=a[lef];lef++;rig–;}else{p=d[lef][c[rig][a[lef]-'a']];q=d[b[lef][a[rig]-'a']][rig];uu=d[lef][rig];if((p<uu)&&(q<uu)){lef++;rig–;}else if((p==uu)&&(q<uu)){rig–;}else if((p<uu)&&(q==uu)){lef++;}else{if(a[lef]>a[rig]){lef++;}else{rig–;}}}}for(i=1;i<=top;i++){printf("%c",ans[i]);}if(lef==rig){printf("%c",a[lef]);}for(i=top;i>=1;i–){printf("%c",ans[i]);}printf("\n");}return 0;}
我没有值得分享的感伤爱情故事，
