最长公共子串

 

/*

 * 好吧，下一题就是LCSubstring.

 * Substring的特点就是必须是连续的。

 *例如X=<A,B,C,D,E>,Y=<B,C,D,A,B>，则LCSubstring为<B,C,D>

 */

public class LongestCommonSubstring {
	
	static String X = " " + "ABCDEABC";
	static String Y = " " + "BCDABEAB";
	public static void main(String[] args) {
		LCS(X, Y);
	}
	
	public static int LCS(String x,String y){
		
		int M = x.length();
		int N = y.length();
		int flagi = 0;
		int flagj = 0;
		char[] X = x.toCharArray();
		char[] Y = y.toCharArray();
		int[][] record = new int[M][N];
		for(int i=0;i<M;i++)
			record[i][0] = 0;
		for(int j=0;j<N;j++)
			record[0][j] = 0;
		int max = 0;
		for(int i=1;i<M;i++){
			for(int j=1;j<N;j++){
				if(X[i] == Y[j]){
					record[i][j] = record[i-1][j-1] + 1;   //注意这里的递推公式
					if(record[i][j]>max){
						max = record[i][j];
						flagi = i;
						flagj = j;
					}
						
				}
					
				else
					record[i][j] = 0;
			}
		}
		
		System.out.println("Print the whole Matrix");
		for(int i=0;i<M;i++){
			for(int j=0;j<N;j++){
				System.out.print(record[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("Flagi = " + flagi);
		System.out.println("Flagj = " + flagj);
		System.out.println("Print one of the LCS");	
		for(int i=max;i>0;i--){
			System.out.print(X[flagi-i+1]);   //可以根据flagi来求得，也可以根据flagj来求得
		}
		System.out.println();
		System.out.println("The max length of LCS is " + max);
		return max;
	}
}

 不仅求得LCS的最大长度，也输出一条LCS

 解题思路是：

LCS[i][j] = LCS[i-1][j-1]+1  X[i]==Y[j]

LCS[i][j] = 0; X[i] != Y[j]

输出LCS的思路是：

利用max标记出最大值的位置，然后根据max值倒推输出，还是利用了对角线思想。