问题描述：如题，给定一个字符串str和其长度n，求该字符串的一个最长公共回文子串的长度（公共子串个公共子序列是两个不同的概念）。并打印出该回文子串。
解答：1，首先给出一个比较直观的解法。根据回文的性质，我们可以把str进行逆转得到str1，然后求str和str1的最长公共子串，那么该子串的长度就是str的最长回文子串的长度，该公共子串就是最长的那个回文子串。也即我们把这个题目转化为求两个字符串str和str1的最长公共子串的问题。我们假设C[i,j]为以str[i]和str1[j]结尾的最长公共子串的长度，那么状态转移方程为：
C[i,j]=0 if(str[i]!=str1[j])C[i,j]=c[i-1,j-1]+1 if(str[i]==str1[j])
初始条件为C[0,0]=0;最初的时间代价为O(n^2)，空间代价为O(n^2)，空间代价还可以优化为O(n)，只需要j的循环式从高往低即可。代码如下：
//求str1和str2的最长公共子串，下标从1算起
void LCS_continue(char *str1,int n1,char *str2,int n2){
int **C=new int*[n1+1];
for(int i=0;i<=n1;i++){
C[i]=new int[n2+1]();
}
int max=0;
int max_index_i=0;
int max_index_j=0;
for(int i=1;i<=n1;i++){
for(int j=1;j<=n2;j++){
if(str1[i]==str2[j])
C[i][j]=C[i-1][j-1]+1;
else
C[i][j]=0;
if(C[i][j]>max){
max=C[i][j];
max_index_i=i;
max_index_j=j;
}
}
}
cout<<"最长公共子串长度为:"<<max<<ends;
if(max>0){
cout<<"子串为:"<<ends;
while(str1[max_index_i]==str2[max_index_j--]){
cout<<str1[max_index_i--]<<ends;
}
}
//free mem
for(int i=0;i<=n1;i++){
delete [] C[i];
}
delete [] C;
}
空间优化：
void LCS_continue_OPM(char *str1,int n1,char *str2,int n2){
int *C=new int[n2+1]();
int max=0;
int max_index_j=0;
for(int i=1;i<=n1;i++){
for(int j=n2;j>0;j--){
if(str1[i]==str2[j])
C[j]=C[j-1]+1;
else
C[j]=0;
if(C[j]>max){
max=C[j];
max_index_j=j;
}
}
}
cout<<"最长公共子串长度为:"<<max<<ends;
if(max>0){
cout<<"子串为:"<<ends;
while(max>0){
cout<<str2[max_index_j--]<<ends;
max--;
}
}
//free mem
delete [] C;
}
2，下面给出一个直观的动规解，