最長共通部分列（LCS）

// 最長共通部分列（LCS）を動的計画法で求める
function lcs(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    
    // DPテーブルを初期化（0で埋める）
    const dp = Array(m + 1).fill(null)
        .map(() => Array(n + 1).fill(0));
    
    // DPテーブルを構築
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[j - 1]) {
                // 文字が一致：斜め上の値 + 1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 文字が不一致：上または左の最大値
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // バックトラックでLCSを構築
    const lcsArray = [];
    let i = m, j = n;
    
    while (i > 0 && j > 0) {
        if (str1[i - 1] === str2[j - 1]) {
            // 文字が一致：LCSに追加して斜め上に移動
            lcsArray.unshift(str1[i - 1]);
            i--;
            j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            // 上の値が大きい（または同じ）：上に移動
            i--;
        } else {
            // 左の値が大きい：左に移動
            j--;
        }
    }
    
    return {
        length: dp[m][n],
        lcs: lcsArray.join('')
    };
}

// 使用例
console.log(lcs("ABCDGH", "AEDFHR"));    // { length: 3, lcs: "ADH" }
console.log(lcs("AGGTAB", "GXTXAYB"));   // { length: 4, lcs: "GTAB" }
console.log(lcs("ABC", "ABC"));          // { length: 3, lcs: "ABC" }
console.log(lcs("ABC", "DEF"));          // { length: 0, lcs: "" }

// DNA配列解析での応用例
function dnaSequenceAlignment(seq1, seq2) {
    const result = lcs(seq1, seq2);
    const similarity = (result.length / Math.max(seq1.length, seq2.length)) * 100;
    
    return {
        ...result,
        similarity: similarity.toFixed(2) + "%"
    };
}

console.log(dnaSequenceAlignment("ATCGATCG", "ATGCATCG"));
// { length: 7, lcs: "ATCATCG", similarity: "87.50%" }

// 複数文字列のLCS（再帰的適用）
function lcsMultiple(strings) {
    return strings.reduce((acc, str) => lcs(acc, str).lcs);
}