Keep on going never give up.

Let's Go

最长公共子序列问题

算法Lonely2020-11-06 00:12:158次0条

著名的最长公共子序列问题(Longest Commom Subsequence,LCS)即寻找序列间最大或最多共同点问题。最长公共子序列算法的主要作用是找出两个序列中最长的公共子序列,是一种非常基础的算法,被广泛应用于程序相似性对比、图形相似处理、媒体流的相似比较、计算生物学等方面。

最长公共子序列问题的定义为:设有两个序列 X[1:m] 和 Y[1:n] ,需要寻找它们之间的一个最长公共子序列。

例如,假定我们有如下两个序列:

X:A B C B D A B

Y:B D C A B A

则 X 和 Y 的一个最长公共子序列为:B C B A

注意:一个子序列不一定必须是连续的,即中间可以被其他字符分开,但它们的顺序必须是正确的。另外,最长公共子序列不一定只有一个,而我们要寻找的是其中的一个最长公共子序列。

显然,最简单的办法是蛮力法求解,对每一个可能的子序列进行检查,看其是否是一个公共子序列,然后在所有的公共子序列里面寻找最长的子序列即可。

蛮力法步骤如下:

(1)检查 X[1:m] 的每一个子序列。

(2)看其是否也是 Y[1:n] 的子序列。

(3)在每一步记录当前找到的子序列里面最长的子序列。

这么一种蛮力策略显然效率十分低下:对每一个子序列的检查需要时间O(n),而总共有2个子序列需要检查,因此,蛮力算法的最坏时间复杂性是O(n×2m),显然,该算法的时间复杂性是指数级的。

通过分析最长公共子序列的性质,可以发现它具有最优子结构性质。因此能设计多项式复杂度的动态规划算法来求解最长公共子序列问题。

image.png

利用动态规划寻找最长公共子序列的步骤为:

(1)先寻找最长公共子序列的长度。

(2)扩展寻找长度的算法来获得最长公共子序列。

策略:考虑序列 X[1:m] 和 Y[1:n] 的前缀序列。


动态规划求解最长公共子序列代码如下:

using System.Text;

namespace ConsoleApp
{
    /// <summary>
    /// 动态规划求最长公共子序列
    /// </summary>
    public class LCS
    {
        /// <summary>
        /// 获取最长公共子序列长度(算法时间复杂性为O(mn),是多项式复杂度,算法的空间复杂性也为O(mn),需要两个二维数组来储存最优值和最优方案)
        /// </summary>
        /// <param name="chA">字符数组 A</param>
        /// <param name="chB">字符数组 B</param>
        /// <param name="pathArray">路径方向</param>
        /// <returns>返回最长公共子序列长度</returns>
        public static int GetLCSLength(char[] chA, char[] chB, out string[,] pathArray)
        {
            pathArray = null;

            int n = chA.Length +1;
            int m = chB.Length +1;

            int[,] lenArray = new int[n,m];
            pathArray = new string[n, m];

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (i == 0 || j == 0)
                    {
                        lenArray[i, j] = 0; //首行 和 首列 初始化赋值为0
                    }
                    else if (i >= 1 && j >= 1)
                    {
                        if (chA[i - 1] == chB[j - 1]) //字符A == 字符B
                        {
                            lenArray[i, j] = lenArray[i - 1, j - 1] + 1; //条件满足,对角线 + 1
                            pathArray[i, j] = "左对角"; // "↖"
                        }
                        else //字符A != 字符B
                        {
                            //条件不满足,继续比较
                            //左方和上方比较,谁大取谁,当左方和上方相等时,默认取上方(最长公共子序列的解不唯一,不一定只有一个解,寻找其中一个最长的公共子序列即可)
                            if (lenArray[i - 1, j] >= lenArray[i, j - 1])
                            {
                                lenArray[i, j] = lenArray[i - 1, j];
                                pathArray[i, j] = "上方"; // "↑"
                            }
                            else
                            {
                                lenArray[i, j] = lenArray[i, j - 1];
                                pathArray[i, j] = "左方"; // "←"
                            }
                        }
                    }
                }
            }

            return lenArray[n - 1, m - 1]; //最长公共子序列长度
        }

        /// <summary>
        /// 获取最长公共子序列字符串(在该算法中,每一次递归调用使 i 或 j 减 1 ,因此该算法的计算时间为O(m+n))
        /// </summary>
        /// <param name="pathArray">路径方向</param>
        /// <param name="i">字符数组 A 长度</param>
        /// <param name="j">字符数组 B 长度</param>
        /// <param name="x">字符数组 A 或 B</param>
        /// <param name="sb">StringBuilder</param>
        public static void GetLCSString(string[,] pathArray,int i,int j,char[] x,StringBuilder sb)
        {
            if (i == 0 || j == 0)
                return;
            if (pathArray[i, j] == "左对角")
            {
                GetLCSString(pathArray,i - 1, j - 1, x, sb);
                sb.Append(x[i - 1]);
            }
            else if (pathArray[i, j] == "上方")
                GetLCSString(pathArray, i - 1, j, x, sb);
            else
                GetLCSString(pathArray, i, j - 1, x, sb);
        }

    }
}

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Linq;
using System.Text;
 
public class ConsoleApp
{
	public static void Main()
	{
		
		Console.WriteLine("请输入序列一:");
        string strA = Console.ReadLine();
        Console.WriteLine("请输入序列二:");
        string strB = Console.ReadLine();
        char[] chA = strA.ToCharArray();
        char[] chB = strB.ToCharArray();
        string[,] pathArray = null;
        int lengt = LCS.GetLCSLength(chA, chB, out pathArray);
        StringBuilder sb = new StringBuilder(1);
        LCS.GetLCSString(pathArray, chA.Length, chB.Length, chA, sb);
        string str = sb.ToString();
        Console.WriteLine($"最长公共子序列为:{str} 长度为:{lengt}");
        Console.ReadKey();
		
	}
	
}



暗锚,解决锚点偏移

文章评论

    嘿,来试试登录吧!