如何找出插入到已知原始字符串中的未知字符串？

方法一：双指针逐字符对比 #

这种方法直观高效，完全匹配你提到的思路，逻辑简单易懂，兼容所有现代浏览器。

逻辑步骤： #

• 初始化两个指针，i 遍历原始字符串 originalString，j 遍历更新后的字符串 updatedString
• 当两个指针指向的字符相等时，同时向后移动
• 遇到字符不相等时，标记插入字符串的起始位置，随后只移动 j 指针，直到再次匹配上 originalString[i] 的字符
• 如果 i 已遍历完原始字符串，updatedString 剩余部分就是插入的字符串

代码实现： #

function findInsertedString(original, updated) {
  let i = 0, j = 0;
  let start = -1;
  const originalLen = original.length;
  const updatedLen = updated.length;

  while (i < originalLen && j < updatedLen) {
    if (original[i] === updated[j]) {
      if (start !== -1) {
        return updated.substring(start, j);
      }
      i++;
      j++;
    } else {
      if (start === -1) {
        start = j;
      }
      j++;
    }
  }

  if (i === originalLen) {
    return updated.substring(j);
  }
  return updated.substring(0, start);
}

// 测试示例
console.log(findInsertedString("pineapple", "piBicycleneapple")); // 输出 "Bicycle"
console.log(findInsertedString("pineapple", "pineapplepear")); // 输出 "pear"
console.log(findInsertedString("pineapple", "applepineapple")); // 输出 "apple"

方法二：字符串匹配简化实现 #

通过定位原始字符串在更新后字符串中的前后匹配片段，快速提取插入内容，代码更简洁。

逻辑步骤： #

• 找到更新后字符串与原始字符串最长的前缀匹配长度
• 如果前缀完全匹配原始字符串，插入部分就是更新后字符串的剩余后缀
• 若前缀未完全匹配，再找到两者最长的后缀匹配长度，中间的部分即为插入内容

代码实现： #

function findInsertedString(original, updated) {
  const originalLen = original.length;
  const updatedLen = updated.length;

  // 计算前缀匹配最大长度
  let prefixLen = 0;
  while (prefixLen < originalLen && prefixLen < updatedLen && original[prefixLen] === updated[prefixLen]) {
    prefixLen++;
  }

  if (prefixLen === originalLen) {
    return updated.slice(prefixLen);
  }

  // 计算后缀匹配最大长度
  let suffixLen = 0;
  while (suffixLen < originalLen - prefixLen && suffixLen < updatedLen - prefixLen) {
    const originalPos = original.length - 1 - suffixLen;
    const updatedPos = updated.length - 1 - suffixLen;
    if (original[originalPos] === updated[updatedPos]) {
      suffixLen++;
    } else {
      break;
    }
  }

  return updated.slice(prefixLen, updatedLen - suffixLen);
}

// 测试示例
console.log(findInsertedString("pineapple", "piBicycleneapple")); // 输出 "Bicycle"
console.log(findInsertedString("pineapple", "pineapplepear")); // 输出 "pear"
console.log(findInsertedString("pineapple", "cherrypineapple")); // 输出 "cherry"

兼容性说明 #

两种方法均使用ES5及以下特性，完全兼容Chrome、Firefox、Safari当前版本，无兼容性顾虑。

内容的提问来源于stack exchange，提问作者Ashley Bischoff