学步园

给定两个序列X和Y，如果Z既是X的子序列，也是Y的子序列，则Z是X与Y的公共子序列，如果Z在X和Y的所有公共子序列中长度最长，则称Z为X和Y 的最长公共子序列。

需要说明的是：公共子序列并不要求在原序列中是连续出现的，只要保证公共子序列在原序列中是顺序出现的即可。

下面的程序是按照算法导论中的思想用Java语言实现的，代码如下所示：

package com.application.sample;
import java.util.List;
import java.util.ArrayList;
public class LCSsearching {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LCSsearching lcs=new LCSsearching();
		String s1="abcbdab";
		String s2="bdcaba";
		lcs.findLCSLength(s1, s2);
	}
	
	public void findLCSLength(String s1,String s2)
	{
		if(s1==null||s2==null)
			return;
		if(s1.length()==0||s2.length()==0)
			return;
		int len1=s1.length();
		int len2=s2.length();
		char[] str1=s1.toCharArray();
		char[] str2=s2.toCharArray();
		int[][] table=new int[len1+1][len2+1];
		Direction[][] direction=new Direction[len1+1][len2+1];
		int i,j;
		for(i=0;i<=len1;i++)
			table[i][0]=0;
		for(j=0;j<=len2;j++)
			table[0][j]=0;
		for(i=1;i<=len1;i++)
		{
			for(j=1;j<=len2;j++)
			{
				if(str1[i-1]==str2[j-1])
				{
					table[i][j]=table[i-1][j-1]+1;
					direction[i][j]=Direction.UPLEFT;
				}else
				{
					if(table[i-1][j]>=table[i][j-1])
					{
						table[i][j]=table[i-1][j];
						direction[i][j]=Direction.UP;
					}else
					{
						table[i][j]=table[i][j-1];
						direction[i][j]=Direction.LEFT;
					}
				}
			}
		}
		searchLCS(direction,str1,len1,len2);
	}
	
	private void searchLCS(Direction[][] direction,char[] str1,int str1length,int str2length)
	{
		int i=str1length,j=str2length;
		if(i==0||j==0)
			return;
		if(direction[i][j]==Direction.UPLEFT)
		{
			searchLCS(direction,str1,i-1,j-1);
			System.out.print(str1[i-1]+" ");
		}else if(direction[i][j]==Direction.UP)
		{
			searchLCS(direction,str1,i-1,j);
		}else
		{
			searchLCS(direction,str1,i,j-1);
		}
	}
	
	private enum Direction{UP,LEFT,UPLEFT}
}

运行结果如下：

b c b a 

从结果我们可以看出，上述算法只是提供了一种求解X与Y的一个最长公共子序列的方法，至于如何求出两个序列的所有最长公共子序列，目前正在研究中，还不知道怎么实现，如果有人研究过的话，可以赐教一下啊呵呵....