stl风格lcs算法.cpp

STL风格LCS算法 STL style LCS algorithm

//STL风格LCS算法
//

//仿 STL 风格利用 random access iterator 实现的最大公共子序列问题求解算法。
//利用该模块通过了ZOJ 1939，算是检验合格。

//

//增加相等判断策略的参数；
// 增加仅求解 LCS 长度的重载版本，节省解构造的开销；
// 若仅求解 LCS 长度，空间复杂度可有 m×n 降低到 2×min(m, n)，
   //其中 m、n 为两个参数序列的长度。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

//
//  Parameters
//
//      first1: An input iterator addressing the position of the first element
//              of the 1st sequence.
//
//      last1:  An input iterator addressing the position one past the last
//              element of the 1st sequence.
//
//      first2: An input iterator addressing the position of the first element
//              of the 2nd sequence.
//
//      last2:  An input iterator addressing the position one past the last
//              element of the 2st sequence.
//
//      result: An output iterator addressing the first element in the 
//              destination range where the LCS is to be stored.
//
//  Return Value
//
//      The length of the LCS.
//
template<
    class InputIterator1
  , class InputIterator2
  , class OutputIterator
>
size_t
longest_common_subsequence( InputIterator1 first1
                          , InputIterator1 last1
                          , InputIterator2 first2
                          , InputIterator2 last2
                          , OutputIterator result )
{
    size_t size1 = ( size_t )distance( first1, last1 );
    size_t size2 = ( size_t )distance( first2, last2 );

    //
    //  dynamic programming for the length of the LCS
    //

    vector<vector<size_t> > len( size1 + 1, vector<size_t>( size2 + 1, 0 ) );

    InputIterator1 it1 = first1;

    for( size_t i = 1; i <= size1; i++, ++it1 ) {
        InputIterator2 it2 = first2;

        for( size_t j = 1; j <= size2; j++, ++it2 )
            if( *it1 == *it2 )
                len[ i ][ j ] = len[ i - 1 ][ j - 1 ] + 1;
            else
                if( len[ i - 1 ][ j ] >= len[ i ][ j - 1 ] )
                    len[ i ][ j ] = len[ i - 1 ][ j ];
                else
                    len[ i ][ j ] = len[ i ][ j - 1 ];
    }

    //
    //  trace back for the LCS
    //

    typedef typename InputIterator1::value_type value_type;

    vector<value_type> lcs;
    size_t i = size1, j = size2, k = len[ size1 ][ size2 ] - 1;

    lcs.reserve( k + 1 );

    while( i && j ) {
        value_type& v1 = *( first1 + i - 1 );
        value_type& v2 = *( first2 + j - 1 );

        if( len[ i ][ j ] == len[ i - 1 ][ j - 1 ] + 1 && v1 == v2 ) {
            lcs.push_back( v1 );
            i--; j--; k--;
        }
        else
            if( len[ i - 1 ][ j ] > len[ i ][ j - 1 ] )
                i--;
            else
                j--;
    }

    copy( lcs.rbegin(), lcs.rend(), result );

    return len[ size1 ][ size2 ];
}

int main( void ) {
    string s1 = "ABCBDAB", s2 = "BDCABA", lcs;

    cout
        << "LCS length is "
        << longest_common_subsequence( s1.begin()
                                     , s1.end()
                                     , s2.begin()
                                     , s2.end()
                                     , back_inserter<string>( lcs ) )
        << endl;

    copy( lcs.begin(), lcs.end(), ostream_iterator<char>( cout ) );

    cout << endl;

    return 0;
}