求给定的字符串中最长回文的长度
#include <stdio.h >
#include <string.h >
#include <iostream.h >
void main(int argc, char* argv[])
{
char *testStr=argv[1];
int i,j;
int a[50][2]; // a[x][0]中间位置,a[x][1]后向指针, 用数组模拟链表
int n=1;
int maxLen=0, maxLenEnd;
a[0][1]=-1; // header
for(i=0;i <strlen(testStr);i++) {
j=0; // 当前节点的前节点
while(true) {
if (a[j][1]==-1)
break;
int tmp=a[j][1]; // 当前节点
// 判断是否还是回文串
if ( !((a[tmp][0]-(i-a[tmp][0]) >=0)
&& (*(testStr+i)==*(testStr+a[tmp][0]-(i-a[tmp][0])))) ) {
// 若不是
if ((i-1-a[tmp][0])*2+1 >maxLen) {
maxLen=(i-1-a[tmp][0])*2+1;
maxLenEnd=i-1;
}
// 删除节点
a[j][1]=a[tmp][1];
continue;
}
j=tmp;
} // end while
// 检查当前是否是回文串
if ((i-2 >0) && (*(testStr+i)==*(testStr+i-2))) {
n++;
a[n-1][0]=i-1;
a[n-1][1]=-1;
a[j][1]=n-1;
}
}
// 剩下的是包含最后一个字符的回文串,
// 只需检查第一个
if (a[0][1]!=-1) {
int tmp=a[0][1];
if ((strlen(testStr)-1-a[tmp][0])*2+1 >maxLen) {
maxLen=(strlen(testStr)-1-a[tmp][0])*2+1;
maxLenEnd=strlen(testStr)-1;
}
}
// 打印结果
cout < <"最长回文串: ";
for(i=maxLenEnd-maxLen+1;i <=maxLen;i++)
cout < <*(testStr+i);
cout < <endl;
cout < <"起始位置:" < <maxLenEnd-maxLen+1 < <" ; " < <"长度:" < <maxLen;
cout < <endl;
}