首页 > 其他 > 详细

Longest Common Subsequence Problem

时间:2015-07-30 07:08:41      阅读:226      评论:0      收藏:0      [点我收藏+]

The longest common subsequence (LCSproblem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

 

LCS function defined[edit]

Let two sequences be defined as follows: X = (x1x2...xm) and Y = (y1y2...yn). The prefixes of X are X1, 2,...m; the prefixes of Y are Y1, 2,...n. Let LCS(XiYj) represent the set of longest common subsequence of prefixes Xi and Yj. This set of sequences is given by the following.

技术分享

To find the longest subsequences common to Xi and Yj, compare the elements xi and yj. If they are equal, then the sequence LCS(Xi-1Yj-1) is extended by that element, xi. If they are not equal, then the longer of the two sequences, LCS(XiYj-1), andLCS(Xi-1Yj), is retained. (If they are both the same length, but not identical, then both are retained.) Notice that the subscripts are reduced by 1 in these formulas. That can result in a subscript of 0. Since the sequence elements are defined to start at 1, it was necessary to add the requirement that the LCS is empty when a subscript is zero.

 

Computing the length of the LCS

The function below takes as input sequences X[1..m] and Y[1..n] computes the LCS between X[1..i] and Y[1..j] for all 1 ≤ i ≤ m and 1 ≤ j ≤ n, and stores it in C[i,j]C[m,n] will contain the length of the LCS of X and Y.

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

Example Question:
http://www.lintcode.com/en/problem/longest-common-subsequence/
http://www.lintcode.com/en/problem/longest-common-substring/

Longest Common Subsequence Problem

原文:http://www.cnblogs.com/midan/p/4688049.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!