算法思想

求字符串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)

按照上面这个公式，我们用容易写出这个算法的实现

算法实现

字符串"blog.csdn.net"和"csdn.blog"求公共子串时的输出结果   

max substr length:5

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

时间空间复杂度分析

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

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

附：完整的源程序g++编译通过

#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]));

       }

       return 0;

}