spoj 1811 Longest Common Substring (后缀自动机)

spoj 1811 Longest Common Substring (后缀自动机)

题意：lcs。。求两个字符串的最长公共连续子串

解题思路：后缀自动机解法。对第一个字符串构造sam，将第二个字符串的字符依次加入sam去匹配。假如我们匹配s2[i]时，匹配到的最大值为temp，在sam上匹配到的位置为p，那当加入s2[i+1]时应该如何更新呢？显然，如果p有指向s2[i]的儿子，temp[i+1] = temp[i] +１，p更新为p->son[k]。如果没有，那么p就沿着fa走，直到p有指向s2[i+1]的儿子，或者p走到NULL。假如p走到了NULL，那么在s2[i+1]这个位置，我们没有匹配到任何字符，故temp[i+1] = 0 , p 走到root。否则，temp[i+1] = val[p] + 1,p更新为p->son[k]。这里temp[i+1]是不能更新为val[q]的（设q=p->son[k]），因为val[q] 并不一定等于val[p] +１，而s2[i]我们只能匹配到p（p沿着fa走，那么很显然，这一路过来的p都能与s2[i]匹配）。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std ;

const int maxn = 250010 ;

struct sam {
	int fa[maxn<<1] , c[26][maxn<<1] , val[maxn<<1] ;
	int dp[maxn<<1] , tot , last ;

	inline int new_node ( int step ) {
		int i ;
		val[++tot] = step ;
		fa[tot] = 0 ;
		for ( i = 0 ; i < 26 ; i ++ ) c[i][tot] = 0 ;
		return tot ;
	}

	void add ( int k ) {
		int i , p = last ;
		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 , int len ) {
		tot = 0 ;
		last = new_node ( 0 ) ;
		int i ;
		for ( i = 0 ; i < len ; i ++ )
			add ( s[i] - 'a' ) ;
	}

	int solve ( char *s ) {
		int len = strlen ( s ) , i ;
		int ret = 0 , pre = 0 ;
		int p = 1 ;
		memset ( dp , 0 , sizeof ( dp ) ) ;
		for ( i = 0 ; i < len ; i ++ ) {
			int k = s[i] - 'a' ;
			if ( c[k][p] ) pre ++ , p = c[k][p] ;
			else {
				while ( !c[k][p] && p ) p = fa[p] ;
				if ( p ) pre = val[p] + 1 , p = c[k][p] ;
				else p = 1 , pre = 0 ;
			}
			ret = max ( ret , pre ) ;
		}
		return ret ;
	}
} suf ;

char s[maxn] ;

int main () {
	while ( scanf ( "%s" , s ) != EOF ) {
		suf.build ( s , strlen ( s ) ) ;
		scanf ( "%s" , s ) ;
		printf ( "%d
" , suf.solve ( s ) ) ;
	}
	return 0 ;
}