题解 | #公共子串计算#

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

/**
 *
 * f(n,m) = {
 *      max(f(n-1,m),f(n,m-1))
 *      相等时, max(比较出来的和, max(f(n-1,m),f(n,m-1)) )
 * }
 */
void (async function () {
    const s1 = await readline();
    const s2 = await readline();
    const datas = getValue(s1, s2);
    console.log(datas[s1.length][s2.length])
})();

function getL(s1, s2) {
    let value = 0;
    for (let k = s1.length - 1; k >= 0; k--) {
        if (
            s1.length - k > s2.length ||
            s1.charAt(k) != s2.charAt(s2.length - s1.length + k)
        ) {
            break;
        }
        value++;
    }
    return value;
}

function getValue(s1, s2) {
    const datas = [];
    for (let i = 0; i <= s1.length; i++) {
        datas[i] = [0];
    }
    for (let i = 1; i <= s2.length; i++) {
        datas[0][i] = 0;
    }

    for (let i = 1; i <= s1.length; i++) {
        for (let j = 1; j <= s2.length; j++) {
            const s1CharAt = i > 0 ? i - 1 : 0;
            const s2CharAt = j > 0 ? j - 1 : 0;
            if (s1.charAt(s1CharAt) !== s2.charAt(s2CharAt)) {
                datas[i][j] = Math.max(datas[i - 1][j], datas[i][j - 1]);
                continue;
            }
            let value = getL(s1.substring(0, i), s2.substring(0, j));
            datas[i][j] = Math.max(value, datas[i - 1][j], datas[i][j - 1]);
        }
        // console.log(i + "行," + datas[i]);
    }

    return datas;
}