• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            FireEmissary

              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              14 隨筆 :: 0 文章 :: 20 評論 :: 0 Trackbacks
             

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

            我實現的算法針對原有的算法輸入需求解耦合,使得算法極度可適配.能用于字符串公共子序列計算和文件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_ContainerR_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_begin0, SectionCommon:: R_begin10, SectionCommon::count5.就表示左邊序列從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());

            }


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

            posted on 2010-03-27 19:31 FireEmissary 閱讀(2830) 評論(1)  編輯 收藏 引用

            評論

            # re: 最長公共子序列的泛型算法 2010-03-28 10:22 expter
            我覺得用c語言直接寫DP還清晰明了點。。。  回復  更多評論
              

            欧美亚洲另类久久综合| 波多野结衣久久精品| 久久精品人人做人人爽电影蜜月| 久久精品国产亚洲AV蜜臀色欲| 精品久久久久久国产| 99国产欧美久久久精品蜜芽| 国产亚州精品女人久久久久久 | 一本色道久久88综合日韩精品 | 亚洲精品无码久久久久去q | 伊人久久大香线蕉av一区| 久久丫精品国产亚洲av| 精品99久久aaa一级毛片| 久久精品国产日本波多野结衣| 国产精品久久久久久久久免费| 亚洲?V乱码久久精品蜜桃 | 亚洲中文字幕久久精品无码喷水 | 国产69精品久久久久APP下载| 久久亚洲国产精品一区二区| 99久久免费国产精品特黄| 中文精品久久久久国产网址| 久久综合久久自在自线精品自| 久久久久亚洲?V成人无码| 成人妇女免费播放久久久| 偷窥少妇久久久久久久久| 国产精品伊人久久伊人电影| 九九精品99久久久香蕉| 亚洲国产精品无码久久SM| 中文字幕精品无码久久久久久3D日动漫 | 久久久久香蕉视频| 激情五月综合综合久久69| 一本大道久久a久久精品综合| 精品熟女少妇av免费久久| 久久精品国产亚洲AV不卡| 欧美精品九九99久久在观看| 久久久久久久综合综合狠狠| 久久久精品国产亚洲成人满18免费网站 | 国产精品美女久久久m| 欧洲人妻丰满av无码久久不卡 | 99久久免费国产精品热| 色偷偷88888欧美精品久久久| 色婷婷综合久久久久中文一区二区|