查找两个字符串中最长的公共子串，可能出现最长长度相同的公共子串！该如何解决

查找两个字符串中最长的公共子串，可能出现最长长度相同的公共子串！！

功能还不是很完善，程序也很笨拙，这里没有用到高级的算法，有没有什么捷径可以让该程序完善？希望高手指点一下，

比如 

char a[]="abcaadybc";
char b[]="kbcdadwbc";
最长公共子串长度是2；满足条件的有bc，ad，bc。（这个bc应该只输出一次就好了）

C/C++ code

#include <stdio.h>#include <stdlib.h>#include <string.h>int longest_length_of_comstr(char *str1, char *str2);int find_the_longest_comstr(char *str1, char *str2);int find_the_longest_comstr(char *str1, char *str2){    int maxlen=longest_length_of_comstr(str1,str2);    int len;        int num=strlen(str1) > strlen(str2) ? strlen(str1)+1 : strlen(str2)+1;    char *p,*q,*tmp1,*tmp2,*maxi;        char *comstr=(char *)malloc(sizeof(char)*num);    for (q=str1; *q!=0; q++)        for (p=str2; *p!=0; p++)        {            len=0;            tmp1=q;            tmp2=p;            while (*tmp1 && *tmp2 && *tmp1==*tmp2)            {                tmp1++;                tmp2++;                len++;            }            if(len == maxlen)            {                maxlen=len;                maxi=q;                                strncpy(comstr,maxi,maxlen);                *(comstr+maxlen)=0;                printf("%s\n",comstr);                break;            }        }    free(comstr);    return 0;}int longest_length_of_comstr(char *str1, char *str2){    int maxlen=0;    int len;    char *p,*q,*tmp1,*tmp2;    for (q=str1; *q!=0; q++)        for (p=str2; *p!=0; p++)        {            len=0;            tmp1=q;            tmp2=p;            while (*tmp1 && *tmp2 && *tmp1==*tmp2)            {                tmp1++;                tmp2++;                len++;            }            if(len > maxlen)            {                maxlen=len;                        }            }    return maxlen;}int main(void){    char a[]="abcaadybc";    char b[]="kbcdadwbc";    find_the_longest_comstr(a,b);    return 0;}

[解决办法]
我试着写了一下，没有用子函数的形式，算法思想比较简单。
以字符数组a作为循环，分别求以a第一个字符、第二个字符，。。。，第strlen（a）个字符打头的最长公共串。从而求出最长公共字串。
写完程序后发现有问题，要是有两个以上且不相等的最长公共串，就出现问题了，不过用二维数组去储存也许不会出现问题，但是问题就变得复杂了。或许真得像楼主一样，先计算出最长公共串的长度再求公共串。

C/C++ code

int main(void){    char a[]="abcaadybc";    char b[]="kbcdadwbc";   // find_the_longest_comstr(a,b);    //先假设b的长度小于a的长度     int i,j,maxLength;    int aLen = strlen(a) ;    int bLen = strlen(b) ;    char *comstr,*tempstr ;    comstr = (char * )malloc(sizeof(char)*bLen) ;    tempstr = (char * )malloc(sizeof(char)*bLen) ;    maxLength = 0 ;    j = 0 ;              for(i=0; i< aLen;i++)    {       int templen = 0 ;        int tempi = 0;         int point = 1 ;          while((tempi < aLen) && (j < bLen))       {               while(a[tempi] == b[j])              {                      tempstr[templen++] = b[j] ;                      tempi++ ;                      j++ ;                          }                            if(templen > maxLength)              {                     maxLength = templen ;                     strcpy(comstr,tempstr) ;                  }                            tempi = i ;              point++ ;              templen = 0 ;                  j = point ;       }          j = 0 ;     }    printf("%s\n",comstr) ;    getchar() ;    return 0;} 

 

查看更多 下一篇