题解 | #查找两个字符串a,b中的最长公共子串#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    let a = await readline();
    let b = await readline();
    const str = getMaxLongSon(a, b);
    // const str = getCommonSeq('jxjelk', 'cmeuvawlwvwxvljvshkoqrtxbywogdnsppuiuezfyliioplpzboanpmilhjqbsocyvhldqrzskjffuofkdzceeoswnmqwfhzbybfsrbkglhfaxxfjvslecjoopxhtfnoziplk')
    console.log(str);
})();

function getMaxLongSon(a, b) {

    if(a.length > b.length){
        let t = a;
        a = b;
        b = t;
    }
    // console.log(b.length)
    let datas = [];
    for (let i = 0; i <= a.length; i++) {
        datas[i] = [""];
        for (let j = 1; j <= b.length; j++) {
            if (i === 0) {
                datas[i][j] = "";
                continue;
            }
            if (a.charAt(i - 1) === b.charAt(j - 1)) {
                const seq = getCommonSeq(a.substring(0, i), b.substring(0, j));
                datas[i][j] =
                    datas[i ][j - 1].length < seq.length
                        ? seq
                        : datas[i ][j - 1]
            } else {
                // if(i == 6 && j == 158){
                //     console.log(123)
                // }
                datas[i][j] = datas[i-1][j].length < datas[i][j -1].length
                        ? datas[i][j-1]
                        : datas[i-1][j];
            }
        }
    }
    // console.log(datas[6][158])
    // console.log(datas[6][157])
    // console.log(datas[5][158])
    return datas[a.length][b.length];

    // return datas[datas.length - 1][datas[0].length - 1];
}

function getCommonSeq(a, b) {
    for (let i = a.length - 1; i >= 0 && b.length - (a.length - i) >=0 ; i--) {
        if (a.charAt(i) !== b.charAt(b.length - 1 - (a.length - 1 - i))) {
            // console.log(a)
            // console.log(b)
            return a.substring(i + 1, a.length);
        }
        // console.log(a.charAt(i))
        // console.log(b)
    }
    return a.length > b.length ? b : a;
}