新建文本文档.txt

参考算法导论写的LCS算法

参考算法导论写的LCS算法，仿照STL的泛型风格，适用于多种STL容器中的各种类型数据构成的序列的最大公共子序列（Longest Common Subsequence）问题求解。

利用该模块AC了ZOJ 1939，算是检验合格了。

 #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 2nd 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;
 }