[求最长公共子串（Longest Common Subsequence, LCS）][解题方法]

 

问题

如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。

       注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。

      请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。

      例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，

              则输出它们的长度4，并打印任意一个子串。

 

 

思想

求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题。

在开始想这道题之前应先理解什么是LCS（最长公共子串）。如串“abcbbc”,"abccbb"，其中的一个字串"abc"是其公共子串，但不时最长公共字串。最长公共子串的定义中，并不要求最长公共子串必须连续出现在两个字符串中，只需要能保持顺序的出现在序列中即可。

 

在理解了什么是LCS之后，LCS的递归解就容易理解了：

c[i,j] =

0  （当 i=0或者j=0）

c[i-1,j-1] +1 （xi = yj，且 i>0,j>0）

Max(c[i,j-1],  c[i-1,j]  ) (xi!=yj , 且i, j >0 )

c[i,j]表示字符串 X[ 1, i]和Y[1, j]的LCS长度。

 

 

 

 

算法导论给出了该算法。算法分成了两步。第一步找到LCS的长度。在找LCS长度的过程中，构造运算矩阵，以方便第二步求解LCS串。

 

扩展

 

    LCS的定义不要求公共子串中的字符连续出现在两个字符串中。如果要求这样做。那么该怎么来做呢。

可以想到和LCS算法差不多的算法。即也维护一个M*N的矩阵c。如果a[i]==b[j],那么c[i][j]=c[i-1][j-1]+1；当i或者j等于0时，c[i][j]=1;如果不等c[i][j]=0。

       代码实现参考代码2。

 

 

代码

 

 

package com.jy.string;

public class LCS {
	public static void main(String[] args) {
		char[] string = "abcbbc".toCharArray();
		char[] string2 = "abccbb".toCharArray();
		
		findLCS(string, string2);
	}
	/**
	 * 
	 * @param string
	 * @param string2
	 */
	public static void findLCS(char[] string ,char[] string2) {
		int m = string.length;
		int n = string2.length;
		int[][] c = new int[m+1][n+1];
		int[][] b = new int[m+1][n+1];
		for(int i=0;i<m;i++) {
			for(int j=0;j<n;j++) {
				if(string[i]==string2[j]) {
					c[i+1][j+1]=c[i][j]+1;
					b[i+1][j+1]= '\\';
				} else {
					if(c[i][j+1] >= c[i+1][j]) {
						c[i+1][j+1] = c[i][j+1];
						b[i+1][j+1]= '|';
					} else {
						c[i+1][j+1] = c[i+1][j];
						b[i+1][j+1]= '-';

					}
				}
			}
		}
		
		System.out.println("LCS长度:"+c[m][n]);
		
		System.out.println("LCS序列:");
		printLCS(b,string,m,n);
	}
	private static void printLCS(int[][] b, char[] string, int i, int j) {
		if(i==0 || j==0) {
			return ;
		}
		
		if(b[i][j]=='\\') {
			printLCS(b, string, i-1, j-1);
			System.out.println(string[i-1]);
		} else if(b[i][j]=='|'){
			printLCS(b, string, i-1, j);
		} else {
			printLCS(b, string, i, j-1);
		}
		 
	}
}

package com.jy.string;

public class LCS2 {
	public static void main(String[] args) {
		findLCS("abcdefg".toCharArray(), "abcdged".toCharArray());
	}
	
	public static void findLCS(char[] string1, char[] string2) {
		int m = string1.length;
		int n = string2.length;
		int[][] c = new int[m][n];
		int max=0;
		int maxPosX = 0;
		for(int i=0;i<m;i++) {
			for(int j=0;j<n;j++) {
				if(string1[i]==string2[j]) {
					if(i==0||j==0) {
						c[i][j] = 1;
					} else {
						c[i][j] = c[i-1][j-1]+1;
					}
					if(c[i][j]>max) {
						max =c[i][j];
						maxPosX = i;
					}
					
				} else {
					c[i][j] = 0;
				}
			}
		}
		System.out.println(max);
		for(int i = maxPosX-max+1;i<=maxPosX;i++) {
			System.out.print(string1[i]);
		}
	}
}