【字符串操作】寻找两个字符串中的最大公共子串

不念不忘少年蓝@ 2022-08-02 10:51 190阅读 0赞

\*题目描述：  
请编写一个函数，求2个字符串的最长公共子串，n<20，字符长度不超过255.  
       例如有2个字符串为：  
       Name some local bus.  
       local bus is high speed I/O bus close to the processor.  
       则最长的公共子串为“local bus”。  
\*要求实现的函数 ：

void find(char* sp, char*dp, char* max_str)

【输入】pIn：输入的字符串  
                      n   ：输入的字符串个数，即数组中元素个数  
      【返回】动态分配的最长公共子串  
      【注意】只需完成该函数功能算法，中间不需要任何IO输入输出  
\*示例  
       输入： pIn\[0\] "what is local bus?"  
       pIn\[1\] "Name some local bus."

实现代码如下：

#include<stdio.h>
    #include<string.h>
    
    void find(char* sp, char*dp, char* max_str)
    {
            int s_len = strlen(sp);
            int d_len = strlen(dp);
            int i=0, j=0,k=0;
            int max_len = -1, tmp_max_len=0;
            int pian_yi_wei = 0;
    
            for(i; i<s_len; i++)
            {
                    for(j=0; j<d_len; j++)
                    {
                            if(sp[i] == dp[j])
                            {
                                     for(k=0; (sp[i+k] == dp[j+k] && sp[i+k]!='\0' && dp[j+k] != '\0'); k++);
    
                                     if(k > max_len)
                                     {
                                                    max_len = k;
                                                    pian_yi_wei = i;
                                     }
                            }
                    }
            }
    
            if(max_len == -1)
            {
                    max_str[0] = '\0';
            }
            else
            {
                      memcpy(max_str, sp+pian_yi_wei, max_len);
                      max_str[max_len] = '\0';
            }
            return ;
    }
    
    
    int  main()
    {
            char str[30]={'\0'};
            find("what is local bus?", "Name some local bus.", str);
            printf("max_str=%s\n", str);
            return 0;
    }

解题思路：

定位一个 游标 ，记录下当前的偏移量 ，也就是 上面 的pianyiwei，

假设k 为最大的长度， 再找到字符相同的时候，逐次 向后偏移,记录最大值， 如果 多个相同最大子串 则保留最开始的。