SPOJ-1811. Longest Common Substr

题目：

http://www.spoj.com/problems/LCS/

http://www.spoj.com/problems/LCS2/

两道水题，据说SA之类的常数卡得挺紧的，于是乎顺手拿过来练手了一下SAM。。。

代码：

1811：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define C( t , x ) sam[ t ].ch[ x ]
#define P( t ) sam[ t ].parent
#define L( t ) sam[ t ].len
#define N( t ) sam[ t ]
 
#define check( ch ) ( ch >= 'a' && ch <= 'z' )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
 
const int maxn = 251000 ;
const int maxv = maxn << 1 ;
 
struct node {
        int ch[ 26 ] , parent , len ;
        node(  ) {
               memset( ch , 0 , sizeof( ch ) ) ;
               parent = len = 0 ; 
        }
} sam[ maxv ] ;
 
int root = maxv - 1 , V = 0 , last = maxv - 1 ; 
 
void add( int ch , int l ) {
        int p = last , np = ++ V ; 
        L( np ) = l ;
        for ( ; ! C( p , ch ) && p ; p = P( p ) ) C( p , ch ) = np ;
        if ( ! p ) P( np ) = root ; else {
               int q = C( p , ch ) ;
               if ( L( q ) == L( p ) + 1 ) P( np ) = q ; else {
                       int r = ++ V ;
                       N( r ) = N( q ) ;
                       L( r ) = L( p ) + 1 ; 
                       P( np ) = P( q ) = r ; 
                       for ( ; p && C( p , ch ) == q ; p = P( p ) ) C( p , ch ) = r ; 
               }
        }
        last = np ;
}
 
int s[ maxn ] , slen ;
 
void getstr(  ) {
        slen = 0 ; 
        int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ; 
        s[ ++ slen ] = ch - 'a' ;
        for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) {
               s[ ++ slen ] = ch - 'a' ;
        }
}
 
int main(  ) {
        getstr(  ) ;
        rep( i , slen ) add( s[ i ] , i ) ;
        int mlen = 0 , ans = 0 , t = root ;
        getstr(  ) ;
        rep( i , slen ) {
               int ch = s[ i ] ;
               if ( C( t , ch ) ) ++ mlen , t = C( t , ch ) ; else {
                       for ( ; t && ! C( t , ch ) ; t = P( t ) ) ;
                       if ( ! t ) t = root , mlen = 0 ; else {
                               mlen = L( t ) + 1 ;
                               t = C( t , ch ) ;
                       }
               }
               ans = max( ans , mlen ) ;
        }
        printf( "%d\n" , ans ) ;
        return 0 ; 
}

1812：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define P( t ) sam[ t ].parent

#define C( t , x ) sam[ t ].child[ x ]

#define N( t ) sam[ t ]

#define F( t ) sam[ t ].fun

#define L( t ) sam[ t ].maxlen

 

const int maxn = 100100 ;

const int maxv = maxn << 1 ; 

 

struct node {

        int child[ 26 ] , parent , fun , maxlen ;

        node(  ) {

               memset( child , 0 , sizeof( child ) ) ;

               parent = fun = maxlen = 0 ; 

        }

} sam[ maxv ] ;

 

int last = maxv - 1 , root = maxv - 1 , V = 0 ; 

 

void extend( int ch ) {

        int np = ++ V , p = last ; 

        L( np ) = L( p ) + 1 ; 

        for ( ; p && ! C( p , ch ) ; p = P( p ) ) C( p , ch ) = np ; 

        if ( ! p ) P( np ) = root ; else {

               int q = C( p , ch ) ;

               if ( L( q ) == L( p ) + 1 ) P( np ) = q ; else {

                       int r = ++ V ;

                       N( r ) = N( q ) ; 

                       L( r ) = L( p ) + 1 ;

                       P( np ) = P( q ) = r ; 

                       for ( ; p && C( p , ch ) == q ; p = P( p ) ) C( p , ch ) = r ; 

               }

        }

        last = np ;

}

 

char s[ maxn ] ;

int dp[ maxv ] , len ;

 

void update( int &x , int val ) {

        x = max( x , val ) ;

}

 

int main(  ) {

        scanf( "%s" , s + 1 ) ;

        len = strlen( s + 1 ) ;

        for ( int i = 0 ; i ++ < len ; ) extend( s[ i ] - 'a' ) ;

        for ( int i = 0 ; i <= V ; ++ i ) dp[ i ] = L( i ) ;

        while ( scanf( "%s" , s + 1 ) != EOF ) {

               len = strlen( s + 1 ) ;

               for ( int i = 0 ; i <= V ; ++ i ) F( i ) = 0 ; 

               for ( int i = 1 , temp = 0 , t = root ; i <= len ; ++ i ) {

                       int ch = s[ i ] - 'a' ;

                       if ( C( t , ch ) ) update( F( t = C( t , ch ) ) , ++ temp ) ; else {

                               for ( ; t && ! C( t , ch ) ; t = P( t ) ) ;

                               if ( ! t ) t = root , temp = 0 ; else {

                                      temp = L( t ) + 1 ; 

                                      update( F( t = C( t , ch ) ) , temp ) ;

                               }

                       }

               }

               for ( int i = V ; i ; -- i ) update( F( P( i ) ) , F( i ) ) ;

               for ( int i = 0 ; i <= V ; ++ i ) dp[ i ] = min( dp[ i ] , F( i ) ) ;

        }

        int ans = 0 ; 

        for ( int i = 0 ; i <= V ; ++ i ) update( ans , dp[ i ] ) ;

        printf( "%d\n" , ans ) ;

        return 0 ; 

}