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 ( "" ) ;
}
}
上一篇:object-c(oc)内存管理机制详解


下一篇:Java强引用、软引用、弱引用及虚引用深入探讨