2774.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2774  User Id:fzk 
Memory:29556K  Time:402MS
Language:C++  Result:Accepted

Source 

#include "stdio.h"
#include "memory.h"
#include "string.h"
#include "stdlib.h"


const int CHAR_NUM = 27;
const int MAXSIZE = 500000;

struct suftree{
	suftree *ch[CHAR_NUM];
	char *l, *r;
	int len;
	suftree *s, *p;
}suft[MAXSIZE];

int use_node = 0;

///////////////////////////////////////////////

suftree *new_node( ) {
	memset( suft+use_node, 0, sizeof(suft[0].ch) );
	suft[use_node].s = 0;
	return suft+(use_node++);
}
suftree *proot;

int get_index( char c ) {
	if( c == '$' )
		return CHAR_NUM-1;
	return c-'a';
}

//	->t	:	->pnew->t 
suftree *disjoin( suftree *t, char *c ) {
	suftree *pnew = new_node( );

	pnew->len = t->p->len + ( c-t->l );
	pnew->l = t->l;
	pnew->r = c;
	pnew->p = t->p;
	pnew->ch[ get_index( *c ) ] = t;

	t->p->ch[ get_index( *(t->l) ) ] = pnew;

	t->l = c;
	t->p = pnew;

	return pnew;
}

/*
	 p ------> s
	/			\
   t			sc
*/
void modify_s( suftree *t ) {
	suftree *s, *p, *sc, *pnew;
	int l1, l2;
	char *l, *r;
	
	if( t->s ) return;
	p = t->p;
	s = p->s;

	if( p == proot && t->r-t->l == 1 ) {
		t->s = proot;
		return;
	}

	l = t->l + ( p == proot );
	r = t->r;

	sc = s->ch[ get_index( *l ) ];
	l1 = ( r - l );
	while( l1 ) {
		l2 = ( sc->r - sc->l );
		if( l1 < l2 ) {
			pnew = disjoin( sc, sc->l+l1 );
			t->s = pnew;
			modify_s( pnew );
			return;
		}
		else {
			if( l1 == l2 ) break;
			l1 -= l2;
			sc = sc->ch[ get_index( l[l2] ) ];
			l += l2;
		}
	}

	t->s = sc;
}

/////////////////////////////////////////////////

void create( char *w, int n ) {
	int i, j;
	char *l, *r = w+n+1, *c;
	suftree *h, *t, *tc; 
	use_node = 0;
	proot = new_node( );

	proot->p = proot->s = proot;
	proot->l = proot->r = w;
	proot->len = 0;
	w[n] = '$';
	w[n+1] = '\0';
	h = proot;

	for( i=0; i<n; i++ ) {
		
		if( i ) {
			l = r - ( h->r - h->l );
			if( l-w < i ) l = w+i;
		}
		else l = w;
		t = h->p->s;		

		while( 1 ) {
			j = get_index( *l );
			tc = t->ch[ j ];

			if( tc == 0 ) {
				tc = new_node( );
				tc->l = l;
				tc->r = r;
				tc->p = t;
				tc->len = t->len + ( r-l );
				t->ch[ j ] = tc;
				modify_s( t );
				break;
			}
			else {
				for( c=tc->l; c<tc->r && *l == *c; c++, l++ )
					;
				if( c >= tc->r )
					t = tc;
				else
					t = disjoin( tc, c );
			}
		}
		h = tc;

	}//for

}
//////////////////////////////////////////////////////////////////////

char word1[100100], word2[100100];
int main( ) {
	int len1, len2, ans = 0, temp, i;
	char *l, *l1, *l2;
	suftree *t, *tc;

	ans = 0;	
	scanf( "%s", word1 );
	scanf( "%s", word2 );
	len1 = strlen( word1 );
	len2 = strlen( word2 );
	create( word1, len1 );

	t = proot;
	l = word2;
	do {
		tc=t->ch[ get_index(*l) ];
		if( tc ) {
			for( l1=tc->l, l2=l; l1<tc->r && *l1==*l2; l1++, l2++ )
				;
			if( ( temp = tc->len - ( tc->r-l1 ) ) > ans )
				ans = temp;
			if( l1 == tc->r )
				t = tc, l = l2;
			else {	
				if( t == proot )
					l++;
				t = t->s;
			}
		}
		else {
			if( t == proot )
				l++;
			t = t->s;
		}
	}while( l < word2+len2 );
	

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

	return 0;
}