HJ75 公共子串计算
题目描述
示例
代码
动态规划，使用一个二维数组记录状态转移
js
/*
计算两个字符串的最长公共子串
asdfas
werasdfaswer
输出：6
最长的子串为 asdfas
使用动态规划，思路参考
https://www.bilibili.com/video/BV1aK411J7b8?from=search&seid=16339578023628360686&spm_id_from=333.337.0.0
构建一个状态转移的二维数组，用来存状态
比如 str1= acgta str2 = aacgttag
我们肉眼可见 最长的公共子串是 acgt，所以最终输出的结果是 长度 4
动态规划构建的状态转移数组如下
a a c g t t a g
0 0 0 0 0 0 0 0 0
a 0 1 1 0 0 0 0 1 0
c 0 0 0 2 0 0 0 0 0
g 0 0 0 0 3 0 0 0 1
t 0 0 0 0 0 4 1 0 0
a 0 1 1 0 0 0 0 1 0
所以输出的就是 4
状态转移的方程为
if(a === b){
table[row][col] = table[row-1][col-1] + 1
} else {
table[row][col] = 0
}
*/
let readline = require('readline')
let rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
})
let inputArr = [] // 记录输入的值
rl.on('line', line=>{
// 记录输入的值
inputArr.push(line)
if(inputArr.length === 2){ // 输入两个字符串的时候，计算结果
let [ str1, str2 ] = inputArr
let len1 = str1.length
let len2 = str2.length
// 初始化一个dp二维数组，全部填充0
let dp = new Array(len1+1).fill([]).map(()=>{
return new Array(len2+1).fill(0)
})
let max = 0 // 默认最大子串长度为0
// 两层循环 开始遍历（从索引1开始遍历，因为要从二维数组的第二行第一列的第一位开始计算）
//（二维数组的第一行第一列是预留的0，为了计算状态）
for(let i = 1; i < len1+1; i++){
for( let j = 1; j < len2+1; j++ ){
let a = str1[i-1]
let b = str2[j-1]
if(a === b){
dp[i][j] = dp[i-1][j-1] + 1
}
// 记录当前最大长度
if(dp[i][j] > max){
max = dp[i][j]
}
}
}
console.log(max)
// 每次计算一次结果后 清空输入输入，便于接下来的计算
inputArr.length = 0
}
})