最长公共子序列-动态规划
参考自http://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97
最长公共子序列,就是找出两个序列中最长的相同序列(不必连续)
比如ABTCK和AECK的最长子序列就是ACK。
查找出最长公共子序列需要一些数学方法。
首先设想,对于两个序列
X:x1,x2,x3....Xm
Y:y1,y2,y3...Yn
假设 Xm 和 Yn 是相同的,那么只需要找到 Xm -1,和ym-1的最长公共子序列,再加上 Yn 就行了。
如果 Xm 和 Yn 不同,那么就要计算2次了
先把 Xm 去掉,用 Xm-1个序列和 Yn 算最长公共子序列。再把 Xm 去掉,用 Yn-1个元素和 Xm 算最长公共子序列。
两种的结果再比较,取较大的那个序列。
因此,可以通过两个for,来比较任意2个子序列之间的最长公共子序列。
如果用数学公式表达,可以表示为
可以用二维数组c[i,j]表示截止到X[i]的字符串与截止到的Y[j] 的字符串的最长公共子序列长度。为了便于编程,我们队c[i,0]和c[0,j]上的元素都初始化为0
编写代码后,可以生成如下的一个表。
先不用去看箭头。
看x2和y1之间的数字,因为都是B,所以这个值就是斜上角的数字+1=1。说明AB和B之间最长公共子序列长度为1.
再看x2和y2,一个B一个D,不相等,那么就因为c[2,1]比c[1,2]大,所以就还是为1.说明AB和BD之间的最长公共子序列还是为1.
依次类推。直至填满整个表格。
箭头可以用另一个二维数组表示,表示这个长度是从哪来计算出来的,用于后期的回溯。
这个表完成后,要获取最长公共子序列就只需要回溯此表。按照箭头的顺序就可以了。
回溯的算法也是依据这样的一个事实,即
如果 Xm = Yn ,那么 Xm 就是最长子序列中的一个值。而且是最后一个值。
然后找到 Xm -1, Yn 或者 Xm , Yn -1这两组各自的最长公共子序列,去长的那个+ Xm 就ok了。
如上图,先找到x7和y6,由于不相同,就找x6和y6之间的。为啥是x6和y6而不是x7,y5,那是因为x6y6和x7y5的最长公共子序列都是4,所以我们就只约定一种取值方式就可以了。如果取x7,y5,则会导致另一种不同的结果。待会可以从代码中看到。
接下来看具体代码和结果。代码的backtrack1和backtrack2其实是等价的。
此处我们定义的是如果(c[i - 1, j] >= c[i, j - 1])就按照向上的路径走。
如果我们改为c[i - 1, j] == c[i, j - 1],则可以看到结过就不同了,但是都是最长公共子序列。
此处用到的算法为动态规划,理解这个算法,需要仔细的看着算法和代码,好好想想,就会明白其中的奥妙。
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- namespace ConsoleApplication2
- {
- public class Program
- {
- static void Main(string[] args)
- {
- string x = "ABCBDAB";
- string y = "BDCABA";
- int lengthx = x.Length + 1;//要多出一维存放0
- int lengthy = y.Length + 1;//要多出一维存放0
- int[,] c = new int[lengthx, lengthy];
- char[,] b = new char[lengthx, lengthy];
- LCSLength(x, y, c, b);//构建最长任意两个字符串之间的子序列
- for (int i = 0; i < lengthx; i++)
- {
- for (int j = 0; j < lengthy; j++)
- {
- Console.Write(c[i, j] + " ");
- }
- Console.WriteLine();
- }
- Console.WriteLine();
- Console.WriteLine();
- for (int i = 0; i < lengthx; i++)
- {
- for (int j = 0; j < lengthy; j++)
- {
- Console.Write(b[i, j] + " ");
- }
- Console.WriteLine();
- }
- Console.WriteLine(backtrack2(b, x, x.Length, y.Length));
- }
- static void LCSLength(string x, string y, int[,] c, char[,] b)
- {
- int i, j;
- for (i = 0; i < x.Length; i++)
- c[i, 0] = 0;
- for (j = 0; j < y.Length; j++)
- c[0, j] = 0;
- for (i = 1; i <= x.Length; i++)
- {
- for (j = 1; j <= y.Length; j++)
- {
- if (x[i - 1] == y[j - 1])//如果当前元素相等。(因为c数组比x,y多一维,所以此处计算都是有-1的,下同)
- {
- c[i, j] = c[i - 1, j - 1] + 1;
- b[i, j] = '↖';//搜狗输入法 //标记b[i,j]是怎么来的。用于回溯。
- }
- else//如果当前元素不相等,分2种情况计算公共子序列的长度
- { //看x去掉末尾元素后,和y序列
- //去掉y序列的最后元素,和x序列
- //谁的长度更长。
- if (c[i - 1, j] >= c[i, j - 1])
- {
- c[i, j] = c[i - 1, j];
- b[i, j] = '↑';//搜狗输入法 //标记b[i,j]是怎么来的。用于回溯。
- }
- else
- {
- c[i, j] = c[i, j - 1];
- b[i, j] = '←';//搜狗输入法 //标记b[i,j]是怎么来的。用于回溯。
- }
- }
- }
- }
- }
- static string backtrack1(int[,] C, string X, string Y, int i, int j)
- {
- if (i == 0 || j == 0)
- return "";
- else if (X[i - 1] == Y[j - 1])
- return backtrack1(C, X, Y, i - 1, j - 1) + X[i - 1];
- else if (C[i, j - 1] > C[i - 1, j])
- return backtrack1(C, X, Y, i, j - 1);
- else
- return backtrack1(C, X, Y, i - 1, j);
- }
- static string backtrack2(char[,] B, string X, int i, int j)
- {
- if (i == 0 || j == 0)
- return "";
- else if (B[i, j] == '↖')
- return backtrack2(B, X, i - 1, j - 1) + X[i - 1];
- else if (B[i, j] == '↑')
- return backtrack2(B, X, i - 1, j);
- else //if (B[i - 1, j - 1] == '←')
- return backtrack2(B, X, i, j - 1);
- }
- }
- }
本文转自cnn23711151CTO博客,原文链接:http://blog.51cto.com/cnn237111/857911 ,如需转载请自行联系原作者