Click here to Skip to main content
12,829,103 members (42,797 online)
Click here to Skip to main content
Add your own
alternative version


14 bookmarked
Posted 25 Mar 2010

Longest Common Subsequence

, 25 Mar 2010 CPOL
Rate this:
Please Sign up or sign in to vote.
Generic algorithm of the longest common subsequence


The classic longest common subsequence algorithm needs the length of two sequences are known. It is usually used to calculate the common sub-sequence of strings.


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


My algorithm is extremely adaptable. It can be used to calculate common subsequence of strings, or file diff calculation. Theoretically it can be used for any two sequences with similar characteristics of longest common subsequence.

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 accepts input iterator. R_Iterator accepts random access iterators. L_Container and R_Container by calling begin () and end () to the first LCS_Calculate .

L_ * Heading refer to the left sequence , R_ * Heading refer to the right sequence .
The last parameter Container & out is used to output sequences of the same section. Typical parameters std:: deque <FEtool::SectionCommon> can also FEtool:: EmptyContainer. If FEtool:: EmptyContainer parameters be chosen a specialization of template code Guarantee does not do back calculation.

LCS_Calculate optimization algorithms work according to the incoming parameter. It requires the right sequence is always the random access iterators, the left of the sequence can be the input iterator. Within the array used in the calculation using the scroll array implementation(LCSArray), space size is the right sequence length * 2.

If the last parameter of LCS_Calculate is not EmptyContainer, it will calculate common section of the sequences. If L_Iterator is not, random access iterators will be used within a dynamic growth array to do back calculation. If L_Iterator is a random access iterator Direct Request space (left sequence size * the right sequence size) is used to support the back calculation.

Points of Interest

struct FEtool::LCS_Compare_Trait defines the comparison algorithm by operator ==. You can customize it.

struct FEtool:: SectionCommon defines the same part of the two sequences. For example, SectionCommon:: L_begin is 0, SectionCommon:: R_begin is 10, SectionCommon:: count is 5. This means that the left sequence of 0 start, and the right sequence from 10 start, 5 data are identical.

Related Resources


  • 25th March, 2010: Initial post


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

China China
No Biography provided

You may also be interested in...

Comments and Discussions

GeneralMy vote of 5 Pin
kazemtnt1-Jul-11 11:12
memberkazemtnt1-Jul-11 11:12 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170326.1 | Last Updated 25 Mar 2010
Article Copyright 2010 by FireEmissary
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid