題目：
http://www.spoj.com/problems/LCS/
http://www.spoj.com/problems/LCS2/
兩道水題适袜，據(jù)說SA之類的常數(shù)卡得挺緊的魏滚，于是乎順手拿過來練手了一下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 ;
}
