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

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

//复杂度更小的解题方式，当长度过长时能节省大量时间
//原理：交错移动较短的字符串，这样所有的子串情况都能遍历到。
//记录最长的重合子串中下标最小的结果
//阶段一：
//efgyiffxoonftmmvd-->
//                exwzdcwjsttuhsxrcpzplpnfqxqsqtlfctdkgacejita

//            efgyiffxoonftmmvd-->
//exwzdcwjsttuhsxrcpzplpnfqxqsqtlfctdkgacejita

//阶段二：
//                              efgyiffxoonftmmvd-->
//exwzdcwjsttuhsxrcpzplpnfqxqsqtlfctdkgacejita
//                                           efgyiffxoonftmmvd-->
//exwzdcwjsttuhsxrcpzplpnfqxqsqtlfctdkgacejita

int main() {
    //这一大段用来将较短字符串赋予arr1,较长子串赋予arr2.(图方便，这段代码可优化)
    char arr3[301];
    char arr4[301];
    scanf("%s", arr3);
    scanf("%s", arr4);
    char* arr1;
    char* arr2;
    int len3 = strlen(arr3);
    int len4 = strlen(arr4);
    if (len3 > len4) {
        arr1 = arr4;
        arr2 = arr3;
    } else {
        arr1 = arr3;
        arr2 = arr4;
    }
    int len1 = strlen(arr1);
    int len2 = strlen(arr2);






    int maxl = 0;//记录历史最大重合子串长度
    int curl = 0;//记录当前重合位置最大的子串长度
    int  target = 0;;//记录最优子串的位置

    int prt1;
    int prt2;
    for (int i = 0; i < len1 + len2; i++) {
        //阶段1的重合方式
        if (i < len1) {
            prt2 = 0;
            prt1 = len1 - i - 1;
            curl = 0;
            while (prt1 < len1 && prt2 < len2) {
                if (arr1[prt1] == arr2[prt2]) {
                    curl += 1;
                } else {
                    //如果当前与历史最长相等，判断是不是下标最小
                    if (maxl == curl) {
                        target = prt1 < target ? prt1 : target;
                    }
                    //如果大于历史最长则直接记录并，记录下标
                    maxl = maxl < curl ? (target = prt1, curl) : maxl;
                    curl = 0;
                }
                prt1++;
                prt2++;

            }
            if (maxl == curl) {
                target = prt1 < target ? prt1 : target;
            }
            maxl = maxl < curl ? (target = (prt1), curl) : maxl;
            curl = 0;
        } 
        //阶段二的重合方式，内容与阶段一相同
        else {
            prt1 = 0;
            prt2 = i - len1 + 1;
            curl = 0;
            while (prt1 < len1 && prt2 < len2) {
                if (arr1[prt1] == arr2[prt2]) {
                    curl += 1;
                } else {
                    if (maxl == curl) {
                        target = prt1 < target ? prt1 : target;
                    }
                    maxl = maxl < curl ? (target = prt1, curl) : maxl;
                    curl = 0;
                }
                prt1++;
                prt2++;

            }
            if (maxl == curl) {
                target = prt1 < target ? prt1 : target;
            }
            maxl = maxl < curl ? (target = (prt1), curl) : maxl;
            curl = 0;
        }

    }
    //依据下表和历史最大长度打印答案
    int bg = target - maxl + 1;
    for (int i = 0; i < maxl; i++) {
        printf("%c", arr1[bg - 1 + i]);
    }
    printf("\n");
    return 0;
}