最长公共子串问题-动态规划

状态转移方程

如果str1[i] == str2[j]，那么dp[i][j] = dp[i-1][j-1];

如果str1[i] != str2[j]，那么dp[i][j] = 0;

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
let arr = [];
let str1;//存储第一行字符串
let str2;//存储第二行字符串
let max = 0;//存储最大公共子串的长度
rl.on('line', function (line) {
    arr.push(line.split(''));
    str1 = arr[0];
    str2 = arr[1];
    if(arr.length==2){
        let dp = new Array(str2.length+1);
        for(let i = 0; i < str2.length+1; i++){//初始化二维数组
            dp[i] = new Array(str1.length+1).fill(0);
        }
        for(let m = 1; m < dp.length; m++){//遍历二维数组
            for(let n = 1; n < dp[0].length; n++){
                if(str2[m-1]==str1[n-1]){//状态转移方程
                    dp[m][n] = dp[m-1][n-1]+1;
                    max = Math.max(max,dp[m][n])
                }
            }
        }
        console.log(max)
    }
});