唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Javascriptで最長共通部分列,Longest Common Subsequence(LCS)の長さを計算

Common Subsequence 解説を素朴に実装.

function LCS(a, b) {
	var sizea = a.length + 1;
	var sizeb = b.length + 1;
	var table = new Array(sizea);
	for(var i = 0; i < sizea; i++) {
		table[i] = new Array(sizeb);
	}
	for(var i = 0; i < sizea; i++) {
		for(var j = 0; j < sizeb; j++) {
			table[i][j] = 0;
		}
	}

	for(var i = 1; i < sizea; i++) {
		for(var j = 1; j < sizeb; j++) {
			match = a[i - 1] == b[j - 1] ? 1 : 0;
			table[i][j] = Math.max(table[i - 1][j - 1] + match, table[i - 1][j], table[i][j - 1]);
		}
	}
	
	return table[a.length][b.length];
}
-->