查看文章
 
求回文长度
2007-10-28 17:21

求给定的字符串中最长回文的长度

#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;
}


类别:默认分类||添加到搜藏 |分享到i贴吧|浏览(127)|评论 (0)
 
最近读者:
 
网友评论:
发表评论:
姓 名:
网址或邮箱: (选填)
内 容:
     

   
帮助中心 | 空间客服 | 投诉中心 | 空间协议
©2012 Baidu