变非回文字符串为回文字符串

接上文的最长回文字串

 

将S变为回文串需要插入的最小字符个数

样例输入与输出

  Ab3bd
   2

 

其实聪明的你已经想到最长公共序列了,不是!就是求两个字符串的相似度.

d[i,j] = min3(d[i-1,j]+1, d[i,j-1]+1,d[i-1,j-1]+cost)

 

这里就是构造编辑矩阵了...

 

 

  

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

int min3(int a, int b, int c)
{
  int min = a;
  if(b<min)
    min = b;
    
  if(c<min)
   min = c;
   
  return min;
}

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)
{
  int i;
  int j;
  int len = strlen(str);
  int c[len+1][len+1];
  int cost = 0;
  int min;
  
  char* revert_str = get_revert(str);
   
  for(i=0;i<len+1;i++)
   c[0][i] = 0;
  
  for(i=0;i<len+1;i++)
   c[i][0] = 0;
 
  for(i=1;i<len+1;i++)
   for(j=1;j<len+1;j++)
    {
      if(str[i-1] == revert_str[j-1])
        cost = 0;
      else
        cost =1;
      
      c[i][j] = min3(c[i-1][j-1]+cost,c[i-1][j]+1,c[i][j-1]+1);
    }
    
    min = c[i-1][j-1];
    free(revert_str);
    return min;
}
     
int main(int argc, char *argv[])
{
  char str[] = "ab3bad";
  char* revert_str = get_revert(str);
   
  printf("str is:%s\n",str);
  
  printf("change to huiwen need %d\n",count_lcs(str));


  system("PAUSE");    
  return 0;
}