您的位置: 首页  >  IT文章  >  查找两个字符串中最长的公共子串，可能出现最长长度相同的公共子串！该如何解决

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

分类: IT文章 • 2022-07-17 09:00:47
查找两个字符串中最长的公共子串，可能出现最长长度相同的公共子串！！

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

比如 

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;
}

相关推荐