寻找最长公共子串

目录

一、试题

二、现实意义

三、实现

四、结果

---

一、试题

给定一个函数，输入两个字符串，找到两者最长公共子串

二、现实意义

实现文本对比，可在类似git等多人代码合并工具中应用

三、实现

js

 //输入
 findLongestCommonSubstring({
  str1: "Saying and doing are two different things",
  str2: "someone said: Saying and doing are two different things,but I have different idea"
 })
 function findLongestCommonSubstring({ str1, str2, L1 = str1.length, L2 = str2.length }) {
  let minL, maxL;
   [maxL, minL] = [L1, L2].sort();
  let findStr = ""; //最长子串
  let indexDis = 0; //索引偏移
  for (let fL = 1; fL <= minL; fL++) {
   // fL 能找到的最长的长度
   let sub1, sub2, idx1, idx2;
   for (idx1 = 0; idx1 < L1 - fL + 1; idx1++) {
    let bk1 = false;
    for (idx2 = 0; idx2 < L2 - fL + 1; idx2++) {
     if (str1.substr(idx1, fL) == str2.substr(idx2, fL)) {
      findStr = str1.substr(idx1, fL);
      indexDis = idx2 - idx1;
      bk1 = true;
      break;
     }
    }
   }
  }
  //打印
  console.log('输入：');
  console.log('str1: ' + str1);
  console.log('str2: ' + str2);
  console.log('=============================')
  console.log('输出：')
  console.log('str1: ' + (indexDis > 0 ? getSpace(indexDis) : '') + str1.replace(new RegExp(findStr), "[" + findStr + "]"));
  console.log('str2: ' + (indexDis < 0 ? getSpace(-indexDis) : '') + str2.replace(new RegExp(findStr), "[" + findStr + "]"));
 }
 /**
  * 空格字符串
  */
 function getSpace(n) {
  let sp = "";
  for (let i = 0; i < n; i++) {
   sp += " ";
  }
  return sp
 }

四、结果