最长连续公共子序列

最长公共子序列可以分成连续的子序列和非连续的子序列，后者在CLRS中称为LCS。这里主要给出的连续的公共子序列的算法及其程序。

主要有3种解法：1) 暴力法； 2) DP(矩阵型—>线型)；3) 后缀树。

1) 简单，不用赘述。

2) Dynamic Programming (连续与不连续情况都适用)

\	e	d	c	e	d	n
n	0	0	0	0	0	1
c	0	0	1	0	0	0
e	1	0	0	1	0	0
d	0	1	0	0	1	0
t	0	0	0	0	0	0

我们把两个字符串看作矩阵的x-y轴：首先遍历字符串时，把两个字符相同的位置标记成1，不相同的地方标记成0。很容易证明，如果能形成公共子序列，则最长子序列一定是从某个位置开始的对角线的长度，所以我们需要做的就是统计对角线的长度。

例如str1=”ncedt”与str2=”edcedn”生成的矩阵如左矩阵，遍历找到最长的对角线即可。

	e	d	c	e	d	n
n	0	0	0	0	0	1
c	0	0	1	0	0	0
e	1	0	0	2	0	0
d	0	2	0	0	3	0
t	0	0	0	0	0	0

其实这里还可以优化，即在生成表格的时候，加上对角线上比它前面的元素，这样一遍遍历就可以生成左图所示矩阵，中间记下最大值便可，省下最后一趟比较，降低时间复杂度；空间复杂度也可降低，其实只要一维的数组便可以了，因为每次更新只用到上面一行(或左边一列，看你程序怎么写了，都可以)。

这个直观上很好理解，但拆分到子问题的思想表达起来比较绕，就转一下别人的文字：

---------------------------------------------------------------------------------------------------------------------

定义f(m, n)为串Xm和Yn之间最长的子字符串的长度并且该子字符串结束于Xm 和 Yn。因为要求是连续的，所以定义f的时候多了一个要求，即字符串结束于Xm 和 Yn。

于是有f(m, 0) = f(0, m) = 0
如果xm != yn, 则f(m, n) = 0
如果xm = yn, 则f(m, n) = f(m-1, n-1) + 1
因为最长字符串不一定结束于Xm 和 Yn末尾，所以这里必须求得所有可能的f(p, q) | 0 <>最大的f(p, q)就是解。依照公式用Bottom-up DP可解。

代码就不写了，简单。但是它与其它的DP填表又有所不同，不是直接得出最大的填到表格最后一格中，而是找出格子中的最大值，其中差别，细细体会。刚开始我在想的时候，就是受了之前的做法的影响，迟迟得不到思路，唉～～

3) 广义后缀树(generalized )

关于后缀树(suffix tree)的材料：

http://www.allisons.org/ll/AlgDS/Tree/Suffix/#demoForm

http://www.answers.com/suffix-tree

http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm#substring

http://www.nist.gov/dads/HTML/suffixtree.html

http://blog.csdn.net/love_apple/archive/2007/02/12/1508758.aspx

广义后缀树只是简单修改，如str1和str2一起建一棵后缀树，然后每个子串标记其出处，最长的来自两个串的子串相连就是最长公共连续子串。后缀树的构建比较复杂，现在还没有时间实现。