题解 | #查找两个字符串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)
});

全部评论

相关推荐

每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务