最长公共子串 (LCS)问题

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

    但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。下面是新的矩阵生成方式：

   当字符匹配的时候，我们并不是简单的给相应元素赋上1，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在 矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。

[root@localhost test]# ./a.out abcde bcdef
String:
        1. abcde
        2. bcdef
                b c d e f
        0 0 0 0 0 0
a 0 0 0 0 0 0
b 0 1 0 0 0 0
c 0 0 2 0 0 0
d 0 0 0 3 0 0
e 0 0 0 0 4 0
max substr length:4

这是程序的输出结果,请注意红色字体

时间空间复杂度分析

如果用n,m表示两个字符串的长度的话，那么算法的 

时间复杂度为O(n*m),空间复杂度也为O(n*m)

附：完整的源程序（gcc编译通过）

#include <stdio.h>

#include <string.h>



void print_table(char *str1,char *str2,int **pf)

{

       int i,j,row,col;

       row = strlen(str1);

       col = strlen(str2);

       printf("\t\t");

       for (i=0; i<col; i++)

              printf("%c\t",str2[i]);



       for (i=0; i<=row; i++)

       {

              for (j=0; j<=col; j++)

              {

                     if (j == 0)

                     {

                            printf("\n");

                            if (i)

                                    printf("%c\t",str1[i-1]);

                            else

                                   printf("\t");

                     }

                     printf("%d\t",pf[i][j]);

              }

       }

}



int commstr(char *str1, char *str2)

/* 返回str1,str2的最长公共之串长度*/

{

       int len1=strlen(str1),len2=strlen(str2),row,col,max=0;

       int **pf = new int*[len1+1];//动态分配一个二维数组作为辅助空间


       for (row=0; row<len1+1; row++)

              pf[row] = new int[len2+1];



       //数组赋初值


       for (row=0; row<len1+1; row++)

              pf[row][0] = 0;

       for (col=0; col<len2+1; col++)

              pf[0][col] = 0;



      for (row=1; row<=len1; row++)

              for (col=1;col<=len2; col++)

              {

                     if (str1[row-1] == str2[col-1])

                     {

                            pf[row][col] = pf[row-1][col-1] + 1;

                            max = pf[row][col] > max ? pf[row][col] : max;

                     }

                     else

                            pf[row][col] = 0;

              }

       print_table(str1,str2,pf);

       //空间回收


       for (row=0; row<len1+1; row++)

              delete[] pf[row];

       delete[] pf;



       return max;

}



int main(int argc,char **argv)

{

       if (argc >= 3)

       {

           printf("String:\n\t1. %s\n\t2. %s\n",argv[1],argv[2]);

           printf("\nmax substr length:%d\n",commstr(argv[1],argv[2]));

       }
       else
       {
            printf("Usage : %s string1 string2 \n", argv[0]);

       }

       return 0;



}