最长回文子串

   首先分析下

       char str[] = "babcdcbaa";

   最长的回文字串为abcdcba,回文就是一个递增,一个是递减,很容易想到把字符串反转.这个时候就是要求这两个字符串的最长公共字串了。blog里以前就写过这个就不多说了

 

  

 

#include <stdio.h>
#include <stdlib.h>

char* get_revert(char* str)
{
  int i = 0;
  int len = strlen(str);
  char* revert = (char*)malloc(len+1);
  
  while(len>0)
   {
    revert[i++] = str[len-1];
    len--;
   }
  revert[i] = '\0';
  
  return revert;
}
   
int count_lcs(char* str, char* revert_str, int* pos, int* max_len)
{
  int i;
  int j;
  int len = strlen(str);
  int c[len+1][len+1];
  
  for(i=0;i<len+1;i++)
   c[0][i] = 0;
  
  for(i=0;i<len+1;i++)
   c[i][0] = 0;
 
  *max_len = 0;
  for(i=1;i<len+1;i++)
   for(j=1;j<len+1;j++)
    {
      if(str[i-1] == revert_str[j-1])
       {
         c[i][j] = c[i-1][j-1] + 1;
         if(c[i][j]>*max_len)
          {
            *max_len = c[i][j];
            *pos = i - *max_len + 1;
          }
       }
      else
       c[i][j] = 0;
    }
}
     
int main(int argc, char *argv[])
{
  int i;
  char str[] = "babcdcbaa";
  char* revert_str = get_revert(str);
  int pos = 0;
  int max_len = 0;
   
  count_lcs(str, revert_str, &pos, &max_len);
  printf("str is:%s\n",str);
  printf("pos is %d, max_len is %d\n", pos, max_len);
  
  printf("huiwen is:\n");
  for(i=0;i<max_len;i++)
   printf("%c",str[i+pos-1]);


  system("PAUSE");    
  return 0;
}


 

   大家可以思考下,如果一个字符串不是回文的,如果我想把它变成回文的,问你要添加or删除多少个字符才能做到....blog下篇给出。

谢谢下面这位网友的指正!!!其实这种解法用动态规划效率也还是O(n^2),本来的想法是假设存在回文了的,这样abcdecba这种不存在回文的字符串是不符合题意的,有点牵强,当时细细想想如果是

abcdexhiihyedcba呢,很明显最大回文是hi,所以可以完全否决这种解法了

 

 

 

 

重新写了个程序

#include <stdio.h>
#include <stdlib.h>

void getmax_symmetric(char* str, int* index, int* max)
{
  int start = 0;
  int end = 0;
  int len = strlen(str);
  int search_left;
  int search_right;
       
  while(start<len)
   {
     end = start;
     while((start+1<len)&&str[end+1]==str[end])
       end++;
    search_left=start;
    search_right=end;

    while ((search_left-1>=0)&&(search_right+1<len)&&str[search_left-1]==str[search_right+1])
     {
       search_left--;
       search_right++;
     }
    
    if (search_right-search_left+1>*max)
     {
      *max = search_right - search_left + 1;
      *index = search_left;
     }
  
    start = end + 1;
  }
}

int main(int argc, char *argv[])
{
  int index = 0;
  int max = 0;
  int i;
  //char str[]="aabcxdefggfedycbaa";

  char str[]="abcxycba";
  
  getmax_symmetric(str, &index, &max);
  
  printf("index is %d, max is %d\n", index, max);
  if(max>1)
  {
   printf("printf symmetric is:\n");
   for(i=index;i<max+index;i++)
     printf("%c", str[i]);
    printf("\n");
  }
  else
    printf("sorry we not found symmetric");
    
  system("PAUSE");    
  return 0;
}


 

大致思路就是由search_left和search_right往两边走