Node.js)백준 9251번: LCS

 

 

 

https://boj.ma/9251

9251번: LCS

 

 

 

LCS 설명 GOAT

 

 

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

 

 

 

 

const [N, M] = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n');
const dp = Array.from(Array(N.length + 1), () => Array(M.length + 1).fill(0));
for (let i = 1; i <= N.length; i++) {
	for (let j = 1; j <= M.length; j++) {
		if (N[i - 1] == M[j - 1]) {
			dp[i][j] = dp[i - 1][j - 1] + 1;
		} else {
			dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
		}
	}
}
console.log(dp[N.length][M.length]);