經典的求公共子序列算法需要兩個序列的長度已知.而且通常用于計算字符串的公共子序列.

我實現的算法針對原有的算法輸入需求解耦合,使得算法極度可適配.能用于字符串公共子序列計算和文件diff計算.理論上能用于任何具備相似特征的兩個序列的公共子序列計算.

LCS_Calculate有三個變種:

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接收一個容器用來輸出序列各段相同的地方.典型的Container參數為std::deque<FEtool::SectionCommon> section;也可以為FEtool:: EmptyContainer.

class EmptyContainer
{
public:
    void push_back(SectionCommon const&){};
    LCS_Size size(){return 0;}
    void clear(){}
};

如果為FEtool:: EmptyContainer參數則通過模板特化代碼選擇不計算兩段序列的相同部分。

struct LCS_Compare_Trait
{
template<typename L,typename R>
static   bool equal(L const& left, R const& right)
        {
            return left==right;
        }
};

定義了比較算法,默認用operator==.你可以在FEtool空間通過特化或偏特化LCS_Compare_Trait:: equal來定制它.

struct SectionCommon
{
    LCS_Size L_begin;
    LCS_Size R_begin;
    LCS_Size count;
    void clear(){L_begin=0;R_begin=0;count=0;}
};

指示兩個序列的相同部分. 比如SectionCommon:: L_begin為0, SectionCommon:: R_begin為10, SectionCommon::count為5.就表示左邊序列從0開始的5個數據，和右邊序列從10開始的5個數據都相同.

LCS_Calculate內部根據傳入參數優化實現.經過對經典的動態規劃解公共子序列算法的考察發現,外圍那個循環只需要遍歷它代表的序列一次；即左邊序列則滿足輸入迭代器即可.它要求右邊序列始終是傳入隨機迭代器.內部計算用到的數組使用了滾動數組(LCSArray)實現,空間占用為右邊序列長度*2.

LCS_Calculate的最后一個參數不為EmptyContainer則會計算公共子序列在左右序列中各段的順序和長度.這里L_Iterator是不是隨機訪問迭代器就會影響到性能了.L_Iterator不是隨機迭代器內部就會用到一個動態增長的輔助數組(TrackArrayDynamic)來做回溯; L_Iterator是隨機迭代器則直接一次申請(左序列*右序列)這么大的空間(TrackArrayStatic)來輔助回溯計算.
而如果LCS_Calculate的最后一個參數為EmptyContainer則會選擇一個空數組(TrackArrayEmpty)實現.TrackArrayEmpty類把所有操作展開為空操作.

所有這些,基于模板來自動選擇.用戶不需要指定不同的函數來優化性能:

template<typename L_Iterator,typename R_Iterator,typename Container/**//*vector<LCS_Section>*/>
LCS_Size LCS_Calculate(L_Iterator lbeg,L_Iterator lend,
                    R_Iterator rbeg,R_Iterator rend,
                    Container &out)
{
    out.clear();
    detail::LCSArray array(rend-rbeg);
   typedef detail::SelectTrackArray<Container,typename std::iterator_traits<L_Iterator>::iterator_category> SelectTrack;//選擇適當的回溯數組
   typename SelectTrack::Array trackArr(SelectTrack::TotalRows(lbeg,lend),array.columns());//選擇適當的回溯數組
    LCS_Size leftSize;
    LCS_Size rightSize;
  for( leftSize=1;lbeg!=lend;++lbeg,++leftSize)//外層只需要是輸入迭代器就可
        for( rightSize=1;rightSize<=array.columns();++rightSize)
        {
            if(LCS_Compare_Trait::equal(*lbeg,*(rbeg+rightSize-1))){
                array(leftSize,rightSize)=array(leftSize-1,rightSize-1)+1;
                trackArr(leftSize,rightSize)=0;
            }
            else if(array(leftSize-1,rightSize)>=array(leftSize,rightSize-1)){
                array(leftSize,rightSize)=array(leftSize-1,rightSize);
                trackArr(leftSize,rightSize)=1;
            }
            else{
                array(leftSize,rightSize)=array(leftSize,rightSize-1);
                trackArr(leftSize,rightSize)=-1;
            }

        }
        detail::LCS_KeepTrack(trackArr,out);

    return array(leftSize-1,array.columns());

}

完整代碼包括測試代碼下載