输出所有的最长公共子序列

现在的位置: 首页 > 综合 > 正文

RSS

输出所有的最长公共子序列

2013年10月29日 ⁄ 综合 ⁄ 共 4636字 ⁄ 字号小中大 ⁄ 评论关闭

请先通过维基百科或其他搜索引擎了解如下知识点，如果已经掌握可直接跳过：

【参考网址：

http://en.wikipedia.org/wiki/Standard_Template_Library

http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

】

1. 最长公共子序列；

2. 最长公共子序列与最长公共子串的区别；

Longest Common Subsequence / Longest Common Substring

3. 求解最长公共子序列的动态规划的算法；

可用动态规划算法求解的问题一般具有两个特点：

1）重叠子问题；

2）最优子结构；

4. 通常用动态规划算法先求最长公共子序列的长度，并将所有子问题的解都保存在一个二维数组中。

例如：

字符串X: abcabcaa

字符串Y: acbacba

m = |X| = 8

n = |Y| = 7

递推表达式：

$LCS\left(X_{i},Y_{j}\right) =\begin{cases} \empty& \mbox{ if }\ i = 0 \mbox{ or } j = 0 \\ \textrm{ ( } LCS\left(X_{i-1},Y_{j-1}\right), x_i)& \mbox{ if } x_i = y_j \\ \mbox{longest}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right)& \mbox{ if } x_i \ne y_j \\\end{cases}$

保存子问题的解（Tabulation）

		a	c	b	a	c	b	a
	0	0	0	0	0	0	0	0
a	0	1	1	1	1	1	1	1
b	0	1	1	2	2	2	2	2
c	0	1	2	2	2	3	3	3
a	0	1	2	2	3	3	3	4
b	0	1	2	3	3	3	4	4
c	0	1	2	3	3	4	4	4
a	0	1	2	3	4	4	4	5
a	0	1	2	3	4	4	4	5

LCS(X,Y) = 5

输出所有的最长公共子序列：

例子：

字串 X = “abcabcaa"

字串 Y = "acbacba"，

它们的所有最长公共子序列：

ababa
abaca
abcba
acaba
acaca
acbaa
acbca

1）按照O(mn)动态规划的算法求出最长公共子序列的长度

子问题的解保存在二维数组dp里
dp[i][j] = { 字串 X 的 1~i 部分与字串 Y 的 1~j 部分的最长公共子序列的长度 }

2)构造字母表

S = { i | i in X or i in Y }

字母表S由出现在字串X和字串Y的所有字符构成的集合。

前面例子中 X 与 Y 构成的字母表S = "abc"。

3）字母表中的字符在两个字串中最后出现的下标

概念可参考Java中String类的lastIndexOf()方法

last1[i][j] = { 到字串 X 下标 i 为止，字母表第 j 个字符在字串 X 中最后一次出现的下标 }
last2[i][j] = { 到字串 Y 下标 i 为止，字母表第 j 个字符在字串 Y 中最后一次出现的下标 }

4）枚举最长公共字串的每一个字符

从两个字串的长度 len1 和 len2 开始枚举字母表 S 中的每一个字符

例如，

t1 = last1[len1][0]

t2 = last2[len2][0]

表示字母表第0个字符在 X 字符串1---len1的最大下标为t1,

在Y 字符串1--len2的最大下标为t2。

若dp[t1][t2] 的值为s1和s2的最大公共子序列长度 cnt ，则表示这个字符即字母表的第0个字符是最长公共子序列的最后一个字符，

并且继续在 t1 - 1 和 t2 - 1 的子问题中寻找符合最大公共子序列长度为为cnt - 1的字符串，依此类推，直到达最长公共子序列为0时结束。

把保存的字符串放入set集合里面，让它按字典序排序；否则继续枚举字母表中的下一个字符。

为什么从最长公共子序列的最后一个字符开始寻找呢？

例如：

”CDCD"

"FUCKC"

它们构成的字母表S = ”UDFCK"
现在枚举字符'C'，它在字母表S中的下标 = 3

last1[0][3] = 0 //下标从0开始

last1[3[3] = 2

last2[2][3] = 2

last2[4][3] = 4

根据’C'在两个字串出现的位置，共有(0, 2)、(0, 4)、 (2,
2) 、(2, 4) 四种可能。

我们舍弃前三个，可以为后续的枚举提供更大的空间。

5)Java语言实现

import java.util.*;

/**
 * The string "abcabcaa" and "acbacba" have longest common subsequences:
 * ababa
 * abaca
 * abcba
 * acaba
 * acaca
 * acbaa
 * acbca
 * @author York
 *
 */

public class LongestCommonSubsequence {
	String source;
	String target;
	int[][] c;
	int[][] last1;
	int[][] last2;
	int lcsLength;
	char[] tmp;
	String alphabet;
	HashSet<String> set = new HashSet<String>();
	
	public LongestCommonSubsequence() {
	}
	
	public LongestCommonSubsequence(String s, String t) {
		this.source = s;
		this.target = t;
	}
	
	public int LCSLength() {
		int m = source.length();
		int n = target.length();
		c = new int[m+1][n+1];
	
		c[0][0] = 0;
		for(int i = 1; i <= m; ++i) {
			c[i][0] = 0;
		}
		for(int j = 1; j <= n; ++j) {
			c[0][j] = 0;
		}
		
		for(int i = 1; i <= m; i++) {
			for(int j = 1; j <= n; j++) {
				if(source.charAt(i-1) == target.charAt(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];
				}
				
			}
		}
		return lcsLength = c[m][n];
	}
	
	private void lastIndexOf(String s, int[][] last) {
		for (int j = 0; j < alphabet.length(); ++j) {
			char c = alphabet.charAt(j);
			for (int i = 1; i <= s.length(); ++i) {
				int lastIndex;
				for (lastIndex = i; lastIndex >= 1; --lastIndex) {
					if(c == s.charAt(lastIndex-1)) {
						last[i][j] = lastIndex;
						break;
					}
				}
				if(lastIndex <= 0) {
					last[i][j] = 0;
				}
			}
		}
	}
	
	private void backTraceAll(int index1, int index2, int len) {
		if(len <= 0) {
			String str = new String(tmp);
			System.out.println("lcs: " + str);
			set.add(str);
			return;
		}
		if(index1 > 0 && index2 > 0) {
			for(int j = 0; j < alphabet.length(); ++j) {
				//字母表中第j个字符最后一次出现在子串source(0, index1)的下标
				int t1 = last1[index1][j];
				int t2 = last2[index2][j];
				//数学证明是？或者给出递归表达式吧
				if(c[t1][t2] == len) {
					tmp[len-1] = alphabet.charAt(j);
					backTraceAll(t1-1, t2-1, len-1);
				}
			}
		}
	}
	
	public void printAll() {
		int m = source.length();
		int n = target.length();
		
		//由两个字符串构成的字母表，包含它们中出现过的所有字符的集合
		//alphabet = {i| i in source or target};
		HashSet<Character> alpha = new HashSet<Character>();
		for(int i = 0; i < m; ++i) {
			alpha.add(source.charAt(i));
		}
		for(int j = 0; j < n; ++j) {
			alpha.add(target.charAt(j));
		}
		int length = alpha.size();
		Character[] characters = new Character[length];
		alpha.toArray(characters);
		char[] chars = new char[length];
		for(int i = 0; i < length; ++i) {
			chars[i] = characters[i];
		}
		alphabet = new String(chars);

		System.out.println("alphabet = " + alphabet);
		
		last1 = new int[m+1][alphabet.length()];
		last2 = new int[n+1][alphabet.length()];
		
		System.out.println("c[][]: ");
		for(int i = 0; i <= m; ++i) {
			for(int j = 0; j <= n; ++j) {
				System.out.print(c[i][j] + "\t");
			}
			System.out.println();
		}
		
		
		lastIndexOf(source, last1);
		lastIndexOf(target, last2);
		
		System.out.println("last1[][]: ");
		for(int i = 0; i <= m; ++i) {
			for(int j = 0; j < alphabet.length(); ++j) {
				System.out.print(last1[i][j] + " ");
			}
			System.out.println();
		}
		
		System.out.println("last2[][]: ");
		for(int i = 0; i <= n; ++i) {
			for(int j = 0; j < alphabet.length(); ++j) {
				System.out.print(last2[i][j] + " ");
			}
			System.out.println();
		}

		
		System.out.println("lcs length = " + lcsLength);
		
		tmp = new char[lcsLength];
		backTraceAll(m, n, lcsLength);
		System.out.println("All longest common sequences: ");
		for(String s: set) {
			System.out.println(s);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("Enter two strings:");
		String str1 = sc.nextLine();
		String str2 = sc.nextLine();
		LongestCommonSubsequence lcs = new LongestCommonSubsequence(str1, str2);
		int max = lcs.LCSLength();
		System.out.println("longest length = " + max);
		lcs.printAll();
	}
}

参考网址：

http://blog.csdn.net/tsaid/article/details/6726698

http://blog.csdn.net/xiaoxiaoluo/article/details/8169533

http://www.cppblog.com/varg-vikernes/archive/2010/09/27/127866.html

【上篇】怎么在SQLServer数据库创建多个ArcSDE服务
【下篇】HTTP的认识2

作者: pollster

该日志由 pollster 于11年前发表在综合分类下，最后更新于 2013年10月29日.
转载请注明: 输出所有的最长公共子序列 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

输出所有的最长公共子序列

作者: pollster

书签

最新文章New

本站推荐

返回首页

		a	c	b	a	c	b	a
	0	0	0	0	0	0	0	0
a	0	1	1	1	1	1	1	1
b	0	1	1	2	2	2	2	2
c	0	1	2	2	2	3	3	3
a	0	1	2	2	3	3	3	4
b	0	1	2	3	3	3	4	4
c	0	1	2	3	3	4	4	4
a	0	1	2	3	4	4	4	5
a	0	1	2	3	4	4	4	5

		a	c	b	a	c	b	a
	0	0	0	0	0	0	0	0
a	0	1	1	1	1	1	1	1
b	0	1	1	2	2	2	2	2
c	0	1	2	2	2	3	3	3
a	0	1	2	2	3	3	3	4
b	0	1	2	3	3	3	4	4
c	0	1	2	3	3	4	4	4
a	0	1	2	3	4	4	4	5
a	0	1	2	3	4	4	4	5

		a	c	b	a	c	b	a
	0	0	0	0	0	0	0	0
a	0	1	1	1	1	1	1	1
b	0	1	1	2	2	2	2	2
c	0	1	2	2	2	3	3	3
a	0	1	2	2	3	3	3	4
b	0	1	2	3	3	3	4	4
c	0	1	2	3	3	4	4	4
a	0	1	2	3	4	4	4	5
a	0	1	2	3	4	4	4	5