最长公共子序列求解

我就是我 2022-05-14 23:10 184阅读 0赞

给定两个序列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的一个最长公共子序列的方法，至于如何求出两个序列的所有最长公共子序列，目前正在研究中，还不知道怎么实现，如果有人研究过的话，可以赐教一下啊呵呵....