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]; }