题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3277
首先将所有字符串串在一次做SA，然后我们对于sa上，枚举每个串的每个后缀，求出有几个该后缀的前缀符合条件，那么就要判定区间里面有多少个不同的数，所幸的是这里只需要求是否该数目>=k，所以对于每个位置记录个L（x），表示[L(x),x]中刚好有k个不同的数，且L（x）最大（参考了CF官方题解），然后CF上的题解是对于每个后缀二分出长度，然后是O（n log^2 n的算法），但是O（n log^2 n）在本题仍然会TLE，那么我们发现枚举后缀的时候，如果后缀c+S有n个前缀合法（c表示一个字符，s表示一个串），那么对于后缀S，至少有n-1个前缀合法（如果c+S有n个前缀出现不小于k次，那么其子串也是），那么我们就用类似求SA里的height一样的方法，记录一下前面的后缀的合法前缀数，然后这样的总复杂度就成了均摊O（n log n），可以AC。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std ;
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )
#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
const int maxn = 201000 , inf = 0x7ffffff ;
int n , k , num[ maxn ] , Beg[ maxn ] , End[ maxn ] , pos = 0 ;
char str[ maxn ] , s[ maxn ] ;
int sa[ maxn ] , Rank[ maxn ] , w[ maxn ] , x[ maxn ] , y[ maxn ] , r[ maxn ] , height[ maxn ] ;
inline void build_sa( ) {
int N , b = 1 , M = 0 , len = pos ;
rep( i , pos ) M = max( M , Rank[ i ] = s[ i ] ) ;
x[ 0 ] = y[ 0 ] = 0 ;
do {
rep( i , pos ) {
x[ i ] = Rank[ i ] , y[ i ] = i + b <= pos ? Rank[ i + b ] : 0 ;
}
b <<= 1 ;
REP( i , 0 , M ) w[ i ] = 0 ;
rep( i , pos ) ++ w[ y[ i ] ] ;
rep( i , M ) w[ i ] += w[ i - 1 ] ;
rep( i , pos ) r[ w[ y[ i ] ] -- ] = i ;
REP( i , 0 , M ) w[ i ] = 0 ;
rep( i , pos ) ++ w[ x[ r[ i ] ] ] ;
rep( i , M ) w[ i ] += w[ i - 1 ] ;
DOWN( i , pos , 1 ) sa[ w[ x[ r[ i ] ] ] -- ] = r[ i ] ;
N = 0 ;
rep( i , pos ) {
if ( i == 1 || x[ sa[ i ] ] != x[ sa[ i - 1 ] ] || y[ sa[ i ] ] != y[ sa[ i - 1 ] ] ) ++ N ;
Rank[ sa[ i ] ] = N ;
}
M = N ;
} while ( N < pos ) ;
int rec = 0 ;
rep( i , pos ) {
for ( ; i + rec <= pos && sa[ Rank[ i ] - 1 ] + rec <= pos && s[ i + rec ] == s[ sa[ Rank[ i ] - 1 ] + rec ] ; ++ rec ) ;
height[ Rank[ i ] ] = rec ;
rec = max( rec - 1 , 0 ) ;
}
}
int st[ maxn << 1 ][ 21 ] , B = 0 ;
inline void Init_rmq( ) {
for ( ; ( 1 << B ) < pos ; B ++ ) ;
rep( i , pos ) st[ i ][ 0 ] = height[ i ] ;
rep( i , B ) rep( j , pos ) {
st[ j ][ i ] = min( st[ j ][ i - 1 ] , st[ j + ( 1 << ( i - 1 ) ) ][ i - 1 ] ) ;
}
}
inline int query( int l , int r ) {
if ( l > r ) return inf ;
int k = int( log2( r - l + 1 ) ) ;
return min( st[ l ][ k ] , st[ r - ( 1 << k ) + 1 ][ k ] ) ;
}
int left[ maxn ] , cnt[ maxn ] , kind = 0 ;
typedef long long ll ;
ll ans = 0 ;
inline bool check( int p , int x ) {
int first , last , L , R , mid ;
if ( height[ p ] < x ) first = p ; else {
L = 1 , R = p ;
while ( R - L > 1 ) {
mid = ( L + R ) >> 1 ;
if ( query( mid , p ) >= x ) R = mid ; else L = mid ;
}
first = R - 1 ;
}
if ( height[ p + 1 ] < x ) last = p ; else {
L = p + 1 , R = pos + 1 ;
while ( R - L > 1 ) {
mid = ( L + R ) >> 1 ;
if ( query( p + 1 , mid ) >= x ) L = mid ; else R = mid ;
}
last = L ;
}
return left[ last ] >= first ;
}
int last ;
int main( ) {
scanf( "%d%d" , &n , &k ) ;
rep( i , n ) {
scanf( "%s" , str ) ;
int len = strlen( str ) ;
Beg[ i ] = pos + 1 , End[ i ] = pos + len ;
REP( j , 0 , ( len - 1 ) ) {
s[ ++ pos ] = str[ j ] ; num[ pos ] = i ;
}
s[ ++ pos ] = '&' ;
}
build_sa( ) ;
Init_rmq( ) ;
memset( cnt , 0 , sizeof( cnt ) ) ;
int rec = 1 ;
rep( i , pos ) {
if ( ! ( cnt[ num[ sa[ i ] ] ] ++ ) ) ++ kind ;
if ( kind >= k ) {
for ( ; kind - ( cnt[ num[ sa[ rec ] ] ] == 1 ) >= k ; kind -= ( cnt[ num[ sa[ rec ] ] ] == 1 ) , -- cnt[ num[ sa[ rec ++ ] ] ] ) ;
left[ i ] = rec ;
} else left[ i ] = 0 ;
}
rep( i , n ) {
ans = last = 0 ;
REP( j , Beg[ i ] , End[ i ] ) {
for ( ; check( Rank[ j ] , last + 1 ) && last <= End[ i ] - j ; ++ last ) ;
ans += ll( last ) ;
last = max( last - 1 , 0 ) ;
}
printf( "%lld " , ans ) ;
}
printf( "\n" ) ;
return 0 ;
}
网友评论