编辑代码

// 设置标准输入接口
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 问题描述：求两个字符串的最长公共子串
// 输入格式：两行字符串
// 输出格式：最长公共子串

void (async function () {
  // 读取两个输入字符串
  const str1 = await readline();
  const str2 = await readline();

  // p记录最长公共子串在str1中的结束位置
  let p = 0;
  // maxLength记录最长公共子串的长度
  let maxLength = 0;

  // 创建二维dp数组，dp[i][j]表示以str1[i-1]和str2[j-1]结尾的最长公共子串长度
  let dp = new Array(str1.length + 1)
    .fill(0)
    .map(() => new Array(str2.length + 1).fill(0));

  // 动态规划求解最长公共子串
  for (let i = 0; i < str1.length; i++) {
    for (let j = 0; j < str2.length; j++) {
      // 如果当前字符相同
      if (str1[i] == str2[j]) {
        // dp[i+1][j+1]等于dp[i][j] + 1
        dp[i + 1][j + 1] = dp[i][j] + 1;
        // 更新最长公共子串的长度和结束位置
        if (dp[i + 1][j + 1] > maxLength) {
          maxLength = dp[i + 1][j + 1];
          p = i + 1; // 记录结束位置
        }
      }
    }
  }

  // 根据结束位置和长度，从str1中截取最长公共子串
  console.log(str1.slice(p - maxLength, p));
})();

// 示例说明：
// 输入：
// abcde
// abgde
// 输出：
// ab
// 解释：
// 两个字符串的最长公共子串是"ab"或"de"
// 代码返回第一个找到的最长公共子串"ab"