javascript实现最长公共子序列实例代码

下面是关于“javascript实现最长公共子序列实例代码”的完整攻略。

完整任务说明

本任务要求实现一个javascript代码，用于寻找两个字符串的最长公共子序列。

功能要求

• 输入两个字符串，比如"abcdfg"和"abdfg"，程序需要输出它们的最长公共子序列。
• 实现的算法需要支持对长度为m和n的字符串进行快速计算，时间复杂度需要为 O(m*n)。

背景知识

• “最长公共子序列”是指在两个或多个序列中都出现的最长的序列。
• “子序列”是指在原序列中删去某些元素后得到的序列，不要求元素在子序列中连续。
• 最长公共子序列是两个字符串的最长公共子序列。

参考实现

下面是一个参考实现，其中使用动态规划的思路实现最长公共子序列。

function longestCommonSubsequence(str1, str2) {
    var m = str1.length;
    var n = str2.length;
    var c = [[]];
    var i, j;
    for (i = 0; i < m; i++) {
        c[i] = [];
        for (j = 0; j < n; j++) {
            if (i === 0 || j === 0) {
                c[i][j] = 0;
            } else if (str1[i - 1] === str2[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            } else {
                c[i][j] = Math.max(c[i][j - 1], c[i - 1][j]);
            }
        }
    }
    var s = "";
    i = m - 1;
    j = n - 1;
    while (i >= 0 && j >= 0) {
        if (str1[i - 1] === str2[j - 1]) {
            s = str1[i - 1] + s;
            i--;
            j--;
        } else if (c[i][j - 1] > c[i - 1][j]) {
            j--;
        } else {
            i--;
        }
    }
    return s;
}

这个实现中，首先根据输入的两个字符串分别计算出它们的长度m和n。然后，创建一个空的数组c，用于记录在两个字符串的不同长度前缀中，最长公共子序列的长度。这个数组的初始化需要用到循环，从0开始遍历。

接下来，再次循环，代码将通过比较str1[i - 1]和str2[j - 1]判断两个字符串当前位置的元素是否相同。如果相同，它就会在c[i - 1][j - 1]的基础上加1; 如果不同，则要在c[i][j - 1]和c[i - 1][j]中选择最大值，作为c[i][j]的值。

最后，代码将使用一个while循环来跟踪最长公共子序列。该while循环从右下角（即最后一个数）开始追踪回溯过程。 如果str1[i - 1]和str2[j - 1]相同，则将它们追加到最长公共子序列中并向左上方移动一步。 如果c[i][j - 1]>c[i - 1][j]，则向左移动；否则向上移动。

示例

例如，输入字符串为"abcdfg"和"abdfg"，它们的最长公共子序列为"abdg"。

longestCommonSubsequence("abcdfg", "abdfg");   // 返回："abdg"

另一个例子是，输入字符串为"abcdefghi"和"befhdbagi"，它们的最长公共子序列为"ebag"。

longestCommonSubsequence("abcdefghi", "befhdbagi"); // 返回："ebag"

以上就是针对“javascript实现最长公共子序列实例代码”的详细攻略。