Chinaunix首页 | 论坛 | 博客
  • 博客访问: 968296
  • 博文数量: 214
  • 博客积分: 10173
  • 博客等级: 上将
  • 技术积分: 1867
  • 用 户 组: 普通用户
  • 注册时间: 2007-06-18 13:48
文章分类

全部博文(214)

文章存档

2012年(1)

2010年(13)

2009年(5)

2008年(98)

2007年(97)

分类: LINUX

2007-11-14 20:46:31

动态规划求解最长公共子串问题

算法思想

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

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

算法实现

     1    int commstr(char *str1, char *str2)

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

     3    {

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

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

     6           for (row=0; row

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

     8   

     9           //数组赋初值

    10           for (row=0; row

    11                  pf[row][0] = 0;

    12           for (col=0; col

    13                  pf[0][col] = 0;

    14   

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

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

    17                  {

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

    19                         {

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

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

    22                         }

    23                         else

    24                                pf[row][col] = 0;

    25                  }

    26           //空间回收    

    27           for (row=0; row

    28                  delete[] pf[row];

    29           delete[] pf;

    30   

    31           return max;                  

    32    }

 



程序的输出

  

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

String:

    1. blog.csdn.net

    2. csdn.blog

        c   s   d   n   .   b   l   o   g  

    0   0   0   0   0   0   0   0   0   0  

b   0   0   0   0   0   0   1   0   0   0  

l   0   0   0   0   0   0   0   2   0   0  

o   0   0   0   0   0   0   0   0   3   0  

g   0   0   0   0   0   0   0   0   0   4  

.   0   0   0   0   0   1   0   0   0   0  

c   0   1   0   0   0   0   0   0   0   0  

s   0   0   2   0   0   0   0   0   0   0  

d   0   0   0   3   0   0   0   0   0   0  

n   0   0   0   0   4   0   0   0   0   0  

.   0   0   0   0   0   5   0   0   0   0  

n   0   0   0   0   1   0   0   0   0   0  

e   0   0   0   0   0   0   0   0   0   0  

t   0   0   0   0   0   0   0   0   0   0  


max substr length:5

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


时间空间复杂度分析

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

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

 

 

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

#include

#include

 

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

              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

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

 

       //数组赋初值

       for (row=0; row

              pf[row][0] = 0;

       for (col=0; 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

              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;

      

}

阅读(1739) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~