spoj 7258 Lexicographical Substring Search (后缀自动机)

spoj 7258 Lexicographical Substring Search (后缀自动机)

题意：给出一个字符串，长度为90000。询问q次，每次回答一个k，求字典序第k小的子串。

解题思路：构造出sam后，类似splay求前驱的做法，不断的逼近答案。我们知道，sam里从s走到某一节点即为一个子串，所以我们在每个节点下记录一个cnt，表示该节点下，能走到的节点有多少个。那么我们在求第k小的子串时，就往下走，枚举当前节点下的26字母节点，若枚举到的节点的cnt+1>=k那么就往该节点走，并输出这条边上的字母（为什么要+1呢？因为走到这个节点就可以是一个子串）。否则k -= cnt[v] + 1 （+1的理由同上）。还有一个问题就是如何快速统计cnt了，这个留个小思考吧，其实方法前面几道题里都用到了，详细讨论请留言。

另外，这题还有个小优化，我们要把空的字母边缩掉，这个大家自己去发现了。我也因为这个T了好几发

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

const int maxn = 90005 ;  

int fa[maxn<<1] , c[26][maxn<<1] , val[maxn<<1] ;  
int last , tot ;
int cnt[maxn<<2] ;  

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

inline int new_node ( int step ) {  
	int i ;  
	val[++tot] = step ;  
	for ( i = 0 ; i < 26 ; i ++ ) c[i][tot] = 0 ;  
	fa[tot] = 0 ;  
	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[q] == val[p] + 1 ) 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[np] = fa[q] = nq ;  
			while ( p && c[k][p] == q ) c[k][p] = nq , p = fa[p] ;  
		}  
	}  
	last = np ;  
}  

void init () {
	tot = 0 ;  
	last = new_node ( 0 ) ;  
}  

char s[maxn] ;  
int pos[maxn<<1] , ws[maxn<<1] , to[maxn<<1] ; 
int main () {  
	scanf ( "%s" , s ) ;
	init () ;  
	int i , len = strlen ( s ) , j ;  
	for ( i = 0 ; i < len ; i ++ ) add ( s[i] - 'a' ) ;  
	for ( i = 1 ; i <= tot ; i ++ ) ws[i] = 0 ;  
	for ( i = 1 ; i <= tot ; i ++ ) ws[val[i]] ++ ;  
	for ( i = 1 ; i <= tot ; i ++ ) ws[i] += ws[i-1] ;  
	for ( i = 1 ; i <= tot ; i ++ ) pos[ws[val[i]]--] = i ;
	for ( i = tot ; i >= 1 ; i -- ) {
		int p = pos[i] ;
		int k = 0 ;
		for ( j = 0 ; j < 26 ; j ++ ) {
			if ( c[j][p] ) {
				cnt[p] += cnt[c[j][p]] + 1 ;
				c[k++][p] = c[j][p] ;
				to[c[k-1][p]] = j + 'a' ;
			}
		}
		c[k][p] = 0 ;
	}
	int q ;
	scanf ( "%d" , &q ) ;
	while ( q -- ) {
		int k ;
		scanf ( "%d" , &k ) ;
		int p = 1 ;
		while ( k > 0 ) {
			i = 0 ;
			while ( c[i][p] ) {
				int r = c[i][p] ;
				if ( cnt[r] + 1 >= k ) {
					printf ( "%c" , to[r] ) ;
					k -- ;
					p = r ;
					break ;
				}
				else k -= cnt[r] + 1 ;
				i ++ ;
			}
		}
		puts ( "" ) ;
	}
}