12,298,267 members (51,056 online)
alternative version

14.2K views
14 bookmarked
Posted

# Longest Common Subsequence

, 25 Mar 2010 CPOL
 Rate this:
Generic algorithm of the longest common subsequence

## Introduction

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.

### Sample

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

## Background

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.

## History

• 25th March, 2010: Initial post

## Share

 China
No Biography provided

## You may also be interested in...

 First Prev Next
 My vote of 5 kazemtnt1-Jul-11 10:12 kazemtnt 1-Jul-11 10:12
 Last Visit: 31-Dec-99 18:00     Last Update: 27-May-16 20:25 Refresh 1