题解 | #查找两个字符串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 arr = [];
    while(line = await readline()){
        arr.push(line);
    }
    if(arr[0] == arr[1]){
        console.log(arr[0]);
        return;
    }
    let duan = '', chang = '';
    if(arr[0].length<arr[1].length){
        duan = arr[0];
        chang = arr[1];
    }else{
        duan = arr[1];
        chang = arr[0];
    }

    let dp = [];
    let max_len = 0;
    let heng = 0, zong= 0;
    for(let i=0;i<=duan.length;i++){
        dp[i] = [];
        for(let j=0;j<chang.length;j++){
            if(i==0||j==0){
                dp[i][j] = 0;
            }else{
                if(duan[i-1] == chang[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if(dp[i][j]>max_len){
                        max_len = dp[i][j];
                        heng = i;
                        zong = j;
                    }
                }else{
                    dp[i][j] = 0;
                }
            }
        }
    }

    // 回溯 取到短串中第一次出现的
    let duan_arr = duan.split('');
    let str = []
    while(dp[heng][zong] != 0){
        str.push(duan_arr[heng-1]);
        heng--;
        zong--;
    }
    str = str.reverse().join('');   // 别忘了reverse，因为是倒着往前回溯的
    console.log(str);

}()