题解 | #查找两个字符串a,b中的最长公共子串#

• 设短的字符串为A(a1 a2 ... a_m)，长的字符串为B(b1 b2 ... b_n);
• 对于A从a1开始，依次将a1-a_m，a1-a_m-1，... a2-a_m,a2-a_m-1....去在字符串B上从第一字符开始滑动搜寻
• 停止条件：

       1. 对于B上长度为nn连续的子串，只要与A中进行匹配的不相同就直接break，紧接着B上的窗向右移动一个

       2.若已经在B中第一次搜索到长度为nn的字串相同，直接break

#include<stdio.h>
#include<string.h>

int main(){
    char s1[301]={0};
    char s2[301]={0};
    char t1[301]={0};
    char t2[301]={0};
    scanf("%s%s",s1,s2);
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int len_tmp1,len_tmp2;
    if(len1<len2){
        len_tmp1 = len1;
        len_tmp2 = len2;
        strcpy(t1,s1);
        strcpy(t2,s2);
    }
    else{
        len_tmp1 = len2;
        len_tmp2 = len1;
        strcpy(t1,s2);
        strcpy(t2,s1);
    }
    int max = 0;
    int start = 0;
    for(int i=0;i<len_tmp1;i++){
        for(int j=len_tmp1-1;j>=i+1;j--){
            int nn = j-i+1;
            for(int k=0;k<len_tmp2-nn+1;k++){
                int f = 1;
                for(int m=0;m<nn;m++){
                    if(t2[k+m]!=t1[i+m]){
                        f=0;
                        break;
                    }
                }
                if(f==1){
                    if(nn>max){
                        max = nn;
                        start = i;
                    }
                    break;
                }
            }
            if(max==nn)
                break;
        }
    }
    
    for(int i= start;i<start+max;i++){
        printf("%c",t1[i]);
    }
}