spoj 1812 lcsII (后缀自动机)

题意：求多个串的lcs，最多10个串，每个串最长10w

解题思路：后缀自动机。先建好第一个串的sam，然后后面的串拿上去跑（这个过程同前一题）。sam上，节点要记录两个信息，先说mi[p]，其意思是p节点能匹配的所有串的最短的长度是多少，那我们如何更新这个mi呢？于是我们要记录另一个信息，mm[p]表示，跑当前串时，所跑到的节点能匹配的最大值，用这个最大值去更新mi。一个串跑完之后，要根据parent树，把mm往fa更新，然后用底下传上来的mm更新mi。怎么更新parent呢？很简单，我们知道，parent tree中父亲的代表串的长度必然比儿子短，所以我们只要根据代表串的长度排序，然后从后往前更新即可。

这题我有个小疑问，我们给mi赋初值时，用INF为何不可？而要用当前节点的val值呢？还望有知道的大神能不吝赐教啊。

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std ;

const int maxn = 311111 ;

int max ( int a , int b ) { return a > b ? a : b ; }

int min ( int a , int b ) { return a < b ? a : b ; }

int wv[maxn<<1] , ws[maxn<<1] ;

int mm[maxn<<1] , mi[maxn<<1] ;

struct sam {

	int fa[maxn<<1] , c[26][maxn<<1] , val[maxn<<1] , pos[maxn<<1] ;

	int tot , last ;

	inline int new_node ( int step ) {

		val[++tot] = step ;

		int i ;

		for ( i = 0 ; i < 26 ; i ++ ) c[i][tot] = 0 ;

		fa[tot] = 0 , mi[tot] = val[tot] ;

		return tot ;

	}

	void add ( int k ) {

		int p = last , i ;

		int np = new_node ( val[p] + 1 ) ;

		while ( p && !c[k][p] ) c[k][p] = np , p = fa[p] ;

		if ( !p ) fa[np] = 1 ;

		else {

			int q = c[k][p] ;

			if ( val[p] + 1 == val[q] ) fa[np] = q ;

			else {

				int nq = new_node ( val[p] + 1 ) ;

				for ( i = 0 ; i < 26 ; i ++ ) c[i][nq] = c[i][q] ;

				fa[nq] = fa[q] ;

				fa[q] = fa[np] = nq ;

				while ( p && c[k][p] == q ) c[k][p] = nq , p = fa[p] ;

			}

		}

		last = np ;

	}

	void build ( char *s ) {

		tot = 0 ;

		last = new_node ( 0 ) ;

		int len = strlen ( s ) , i ;

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

		for ( i = 1 ; i <= tot ; i ++ ) wv[val[i]] ++ ;

		for ( i = 1 ; i <= tot ; i ++ ) wv[i] += wv[i-1] ;

		for ( i = 1 ; i <= tot ; i ++ ) ws[wv[val[i]]--] = i ;

	}

	void work ( char *s ) {

		int len = strlen ( s ) ;

		int p = 1 , i , temp = 0 ;

		for ( i = 0 ; i < len ; i ++ ) {

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

			if ( c[k][p] ) temp ++ , p = c[k][p] ;

			else {

				while ( p && !c[k][p] ) p = fa[p] ;

				if ( !p ) temp = 0 , p = 1 ;

				else temp = val[p] + 1 , p = c[k][p] ;

			}

			mm[p] = max ( mm[p] , temp ) ;

		}

		for ( i = tot ; i >= 1 ; i -- ) {

			p = ws[i] ;

			mi[p] = min ( mi[p] , mm[p] ) ;

			if ( fa[p] && mm[fa[p]] < mm[p] ) mm[fa[p]] = mm[p] ;

			mm[p] = 0 ;

		}

	}

	int solve () {

		int i , ans = 0 ;

		for ( i = 1 ; i <= tot ; i ++ )

			ans = max ( ans , mi[i]) ;

		return ans ;

	}

} suf ;

char s[maxn] ;

int main () {

//	freopen ( "a.txt" , "r" , stdin ) ;

	scanf ( "%s" , s ) ;

	suf.build ( s ) ;

	int cnt = 0 ;

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

		suf.work ( s ) ;

	//	cnt ++ ;

	//	if ( cnt == 2 ) break ;

	}

	printf ( "%d\n" , suf.solve () ) ;

}

/*

skds

fkds

aajfaa

*/

巴特西

spoj 1812 lcsII (后缀自动机)

最新文章

热门文章