最长公共子序列

• 下载源代码 - 91.25 KB

引言

经典的 longest common subsequence (最长公共子序列) 算法需要知道两个序列的长度。它通常用于计算字符串的公共子序列。

示例

left sequence :"1233434printSection(SectionCommon"
right sequence:" using printSection(SScpeardectionCommon::"
output:"printSection(SectionCommon"
LCS size=27(include '\0')

背景

我的算法具有极强的适应性。它可以用于计算字符串的公共子序列，或者文件差异计算。从理论上讲，它可以用于任何具有最长公共子序列相似特征的两个序列。

Using the Code

template<typename L_Iterator,typename R_Iterator,typename Container> 
LCS_Size FEtool::LCS_Calculate(L_Iterator lbeg,L_Iterator lend,
    R_Iterator rbeg,R_Iterator rend, Container &out); 
template<typename L_Iterator,typename R_Container,typename Container> 
inline LCS_Size FEtool::LCS_Calculate(L_Iterator lbeg,L_Iterator lend,
    R_Container const&rcontainer, Container &out); 
template<typename L_Container,typename R_Container,typename Container> 
inline LCS_Size FEtool::LCS_Calculate(L_Container const& lcontainer,
    R_Container const&rcontainer, Container &out);

L_Iterator 接受输入迭代器。R_Iterator 接受随机访问迭代器。L_Container 和 R_Container 通过调用 begin () 和 end () 来传递给 LCS_Calculate 。

L_ * 前缀表示左侧序列，R_ * 前缀表示右侧序列。
最后一个参数 Container & out 用于输出相同部分的序列。典型的参数 std:: deque <FEtool::SectionCommon> 也可以是 FEtool:: EmptyContainer。如果选择 FEtool:: EmptyContainer 参数，模板代码的特化版本将保证不进行回溯计算。

LCS_Calculate 优化算法根据传入的参数工作。它要求右侧序列始终是随机访问迭代器，而左侧序列可以是输入迭代器。在计算中使用的数组使用滚动数组实现(LCSArray)，空间大小为右侧序列长度 * 2。

如果 LCS_Calculate 的最后一个参数不是 EmptyContainer，它将计算序列的公共部分。如果 L_Iterator 不是随机访问迭代器，将使用动态增长的数组进行回溯计算。如果 L_Iterator 是随机访问迭代器，则直接请求空间 (左侧序列大小 * 右侧序列大小) 以支持回溯计算。

关注点

结构体 FEtool::LCS_Compare_Trait 通过 operator == 定义了比较算法。您可以自定义它。

结构体 FEtool:: SectionCommon 定义了两个序列的相同部分。例如，SectionCommon:: L_begin 是 0，SectionCommon:: R_begin 是 10，SectionCommon:: count 是 5。这意味着左侧序列从 0 开始，右侧序列从 10 开始，有 5 个数据相同。

相关资源

• http://www.algorithmist.com/index.php/Longest_Common_Subsequence
• http://www.ics.uci.edu/~eppstein/161/960229.html

历史

• 2010年3月25日：初始发布