最长公共字符串

 

问题描述：

最长公共子串 (LCS-Longest Common Substring)

    LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置。

算法思想：

求字符串str1,str2的最长公共子串的长度。

定义二元函数函数f(m,n)：分别以str1[m],str2[n]结尾的连续公共子串的长度

而对于f(m+1,n+1) 有以下两种情况

1.str1[m+1] != str2[n+1],则有f(m+1,n+1) =0

2.str1[m+1] == str2[n+1],则有f(m+1,n+1) = f(m,n) + 1

另外f(0,j) = 0(j>=0)

       f(j,0) = 0 (j>=0)

 

 

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

#define MIN(a,b) a<b ? a : b

char* count_lcs(char* str1, char* str2)
{
  int len1 = strlen(str1);
  int len2 = strlen(str2);
  int i;
  int j;
  int max = 0;
  int A[len1+1][len2+1];
  
  int total = MIN(len1,len2);
  char* ret = (char*)malloc(total+1);
  
  for(i=0;i<len1+1;i++)
    A[i][0] = 0;
  for(j=1;j<len2+1;j++)
    A[0][j] = 0;
  
  for(i=1;i<len1+1;i++)
    for(j=1;j<len2+1;j++)
     {
       if(str1[i-1] == str2[j-1])
       {
         A[i][j] = A[i-1][j-1]+1;
         if( A[i][j]>max )
          {
            ret[max] = str1[i-1];
            max = A[i][j];
           }
        }
       else
        A[i][j] = 0;
      }
    
    ret[max] = '\0';
    
  return ret;
}

int main(int argc, char *argv[])
{
  char* str1 = "abcdfghij";
  char* str2 = "fghijklabcd";
  
  printf("str1:%s\tstr2:%s lcs is %s\n",str1,str2,count_lcs(str1,str2));
  system("PAUSE");    
  return 0;
}


 

又是梅总的提示,str1,str2改变时,lcs会错误,虽然max是对的.考虑的不周到.每次max最大后只是把ret[max-1]赋值了,之前的值没有改变.修改代码如下:

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

#define MIN(a,b) a<b ? a : b

char* count_lcs(char* str1, char* str2)
{
  int len1 = strlen(str1);
  int len2 = strlen(str2);
  int i;
  int j;
  int max = 0;
  int k;
  int A[len1+1][len2+1];
  
  int total = MIN(len1,len2);
  char* ret = (char*)malloc(total+1);
  
  for(i=0;i<len1+1;i++)
    A[i][0] = 0;
  for(j=1;j<len2+1;j++)
    A[0][j] = 0;
  
  for(i=1;i<len1+1;i++)
    for(j=1;j<len2+1;j++)
     {
       if(str1[i-1] == str2[j-1])
       {
         A[i][j] = A[i-1][j-1]+1;
         if( A[i][j]>max )
         {
            max = A[i][j];
            k = max;
            while(k>=0)
            {
              ret[k] = str1[i+k-max];
              k--;
            }
          }
        }
       else
        A[i][j] = 0;
      }
    printf("max is %d\n",max);
    ret[max] = '\0';
    
  return ret;
}

int main(int argc, char *argv[])
{
  char* str1 = "abcdfghij";
  char* str2 = "fghijklabcd";
  
  printf("str1:%s\tstr2:%s lcs is %s\n",str1,str2,count_lcs(str1,str2));
  system("PAUSE");    
  return 0;
}