Longest Common Subsequence

lcs.md

##Longest Common Subsequence

动态规划

设序列X= < x1, x2, …, xm > 和 Y= < y1, y2, …, yn > 的一个最长公共子序列Z= < z1, z2, …, zk >，则：

• 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列
• 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列
• 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列

其中Xm-1= < x1, x2, …, xm-1 > ，Yn-1= < y1, y2, …, yn-1 > ，Zk-1= < z1, z2, …, zk-1 >

不再使用《算法导论》中采用的辅助数组构造输出串，直接由C数组构造

    #include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    string LCS(string a,string b)
    {
    	const int lenA = a.size();
    	const int lenB = b.size();
    
    	vector<vector<int>> c(lenA+2,vector<int>(lenB+2,0));
    	/*
    	//  字符串从 0 开始，数组从1开始，0作占位符，初始化为0
    	//  最后一行和最后一列亦作为占位符使用，用于从c数组构造输出字符串
    	//
        //              /      0                               if i<0 or j<0  
        //    c[i,j]=          c[i-1,j-1]+1                    if i,j>=0 and xi=xj  
        //             /       max(c[i,j-1],c[i-1,j]           if i,j>=0 and xi≠xj  
    	*/
    	for(int i = 1 ; i <= lenA ; i++)
    	{
    		for(int j = 1 ; j <= lenB ; j++)
    		{
    			if(a[i-1] == b[j-1])
    			{
    				c[i][j] = c[i-1][j-1] + 1;
    			}
    			else if(c[i-1][j] >= c[i][j-1])
    			{
    				c[i][j] = c[i-1][j];
    			}
    			else
    			{
    				c[i][j] = c[i][j-1];
    			}
    		}
    	}
    	int i=1,j=1;
    	string result = "";
    	while(i <= lenA && j <= lenB)
    	{
    		if(a[i-1] == b[j-1])
    		{
    			result += a[i-1];
    			i++;
    			j++;
    		}
    		else if(c[i+1][j] >= c[i][j+1])
    		{
    			i++;
    		}
    		else
    		{
    			j++;
    		}
    	}
    	return result;
    }
    
    int main()
    {
    
    	cout<<LCS("ABCBDA","BDCABA")<<endl;
    	system("pause");
    	return 0;
    }