题解 | #查找两个字符串a,b中的最长公共子串#
查找两个字符串a,b中的最长公共子串
https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506
const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const inputs = []; rl.on("line", function (line) { inputs.push(line); }); rl.on("close", function () { const [str1, str2] = inputs; let short: string = str1.length > str2.length ? str2 : str1; let long = str1.length > str2.length ? str1 : str2; let maxStr = ""; const dp = []; for (let y = 0; y < short.length; y++) { const curShort = short[y]; if (!dp[y]) { dp[y] = []; } for (let x = 0; x < long.length; x++) { const curLong = long[x]; if (curShort === curLong) { if (x === 0 || y === 0) { dp[y][x] = 1; } else { dp[y][x] = dp[y - 1][x - 1] + 1; } maxStr = maxStr.length >= dp[y][x] ? maxStr : short.substring(y - dp[y][x]+1, y + 1); // console.log(maxStr); } else { // console.log(x,y,JSON.stringify(dp)) dp[y][x] = 0; } } } // console.log(dp); console.log(maxStr) });