题解 | #查找两个字符串a,b中的最长公共子串#
查找两个字符串a,b中的最长公共子串
https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506
#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; }