题解 | #公共子串计算#

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
    // 方法1：暴力破解
    //避坑： 默认的方法取不到值，不是空格输入的值，是两个readline获取的a,b字符串

    // let a = await readline(); 
    // let b = await readline();
    // 让 a 是短的
    // if (a.length > b.length) {
    //     [a, b] = [b, a];
    // }

    // var maxLen = 0;
    // for (var i = 0; i < a.length; i++) {
    //     for (var j = i; j <= a.length; j++) { // substring 左包右不包 ， 所以j<= a.lenght
    //         var str = a.substring(i, j); // 获取每一段字符串
    //         if (b.indexOf(str) > -1 && j - i > maxLen) {
    //             maxLen = j - i;
    //         }
    //     }
    // }
    // console.log(maxLen);

    /**
     * 方法2: LCS: Longest Common Subsequence 最长公共子序列
     *  str1 = ABC , str2 = BCD ,只要能把下面这个数组构建出来,取最大值就是答案。
     *     B C D
     *   A 0 0 0
     *   B 1 1 1
     *   C 1 2 2
     *   
     *   1. A 与 BCD 比较 都是0 
     *   2. AB 与 BCD 比较 , AB 与 B < BC< BCD 的LCS关系，也就是LCS长度由横向的长度决定。
     * 
     *   LCS 的值一定大于 上 与 左 LCS ,因为它们是从前面来的,至于长度是否要加1，由后一位(x,y)轴是否相等来决定
     * 
     * 
     * str1: x1,x2...xm
     * str2: y1,y2...yn
     * lcs:  z1,z2...zk 
     *
     * 1.如果最后一位相等，已知 abcd,bcd的LCS是bcd,那么把最后一位去掉，就可以得出abc与bc的LCS是bc,
     *   即：lcs(k) = lcs(m-1 ,n-1) + 1
     * 2.如果 abcd,abce,最后一位不相等，则它们的lcs要么是m-1,要么是n-1, 也就是他们比较取个最大
     *   即：lcs(k) = max(lcs(m-1),lcs(n-1))
     *   怎么理解呢？就是str1与str2的lcs长度，要么是str1.length-1,要么是str2.length-1,
     * 
     * 
     *   总结：最后一位相等则LCS是 斜着的值+1
     *         最后一位不等,则是上面的值减一，或左边的值减一 max(i-1,j-1)
     */
    let a = await readline(); 
    let b = await readline();
    let m = a.length
    let n = b.length
    let c = Array.from(Array(m+1),()=>Array(n+1).fill(0));
    let res = 0
    for(var i =1;i<m+1;i++){
        for(var j =1;j<n+1;j++){
            if(a[i-1] == b[j-1]){ // i j 字符匹配则来自左上 + 1
                 c[i][j] = c[i-1][j-1] + 1
                 if( c[i][j] >res){
                    res =  c[i][j] 
                 }
            }
            // else{
            //     c[i][j] = Math.max(c[i-1][j],c[i][j-1])
            // }
        }
    }
    console.log(res) 

})();