[HDU] 4691 Front compression 접미사 배열 + RMQ
3101 단어 HDU
제목 분석: 우선 접두사 그룹을 구성한 다음에height 그룹을 rmq예처리한 다음에 매번 검색할 때마다 O(1)입니다.
코드는 다음과 같습니다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
const int MAXN = 100005 ;
char s[MAXN] ;
int t1[MAXN] , t2[MAXN] , c[MAXN] , xy[MAXN] ;
int sa[MAXN] , rank[MAXN] , height[MAXN] ;
int minv[MAXN][17] ;
int n , m ;
int cmp ( int *r , int a , int b , int d ) {
return r[a] == r[b] && r[a + d] == r[b + d] ;
}
void getHeight ( int n , int k = 0 ) {
For ( i , 0 , n ) rank[sa[i]] = i ;
rep ( i , 0 , n ) {
if ( k ) -- k ;
int j = sa[rank[i] - 1] ;
while ( s[i + k] == s[j + k] ) ++ k ;
height[rank[i]] = k ;
}
}
void da ( int n , int m = 128 ) {
int *x = t1 , *y = t2 ;
rep ( i , 0 , m ) c[i] = 0 ;
rep ( i , 0 , n ) ++ c[x[i] = s[i]] ;
rep ( i , 1 , m ) c[i] += c[i - 1] ;
rev ( i , n - 1 , 0 ) sa[-- c[x[i]]] = i ;
for ( int d = 1 , p = 0 ; p < n ; d <<= 1 , m = p ) {
p = 0 ;
rep ( i , n - d , n ) y[p ++] = i ;
rep ( i , 0 , n ) if ( sa[i] >= d ) y[p ++] = sa[i] - d ;
rep ( i , 0 , m ) c[i] = 0 ;
rep ( i , 0 , n ) ++ c[xy[i] = x[y[i]]] ;
rep ( i , 1 , m ) c[i] += c[i - 1] ;
rev ( i , n - 1 , 0 ) sa[-- c[xy[i]]] = y[i] ;
swap ( x , y ) ;
p = 0 ;
x[sa[0]] = p ++ ;
rep ( i , 1 , n ) x[sa[i]] = cmp ( y , sa[i - 1] , sa[i] , d ) ? p - 1 : p ++ ;
}
getHeight ( n - 1 ) ;
}
void rmq_init ( int n ) {
For ( i , 1 , n ) minv[i][0] = height[i] ;
for ( int j = 1 ; ( 1 << j ) <= n ; ++ j ) {
for ( int i = 1 ; i + ( 1 << j ) - 1 <= n ; ++ i ) {
minv[i][j] = min ( minv[i][j - 1] , minv[i + ( 1 << ( j - 1 ) )][j - 1] ) ;
}
}
}
int rmq ( int L , int R ) {
int k = 0 ;
while ( ( 1 << ( k + 1 ) ) <= R - L + 1 ) ++ k ;
return min ( minv[L][k] , minv[R - ( 1 << k ) + 1][k] ) ;
}
int lcp ( int a , int b ) {
if ( a == b ) return n - a ;
int x = rank[a] , y = rank[b] ;
return x < y ? rmq ( x + 1 , y ) : rmq ( y + 1 , x ) ;
}
int count ( int n , int n1 = 0 ) {
for ( n1 = n ? 0 : 1 ; n ; n /= 10 ) ++ n1 ;
return n1 ;
}
void solve () {
n = strlen ( s ) ;
LL ans1 = 0 , ans2 = 0 ;
int x , y , a , b ;
da ( n + 1 ) ;
rmq_init ( n ) ;
scanf ( "%d" , &m ) ;
scanf ( "%d%d" , &x , &y ) ;
ans1 += y - x + 1 ;
ans2 += y - x + 3 ;//y - x + 2 + count ( 0 ) - 0 ;
while ( -- m ) {
scanf ( "%d%d" , &a , &b ) ;
ans1 += b - a + 1 ;
int tmp = min ( lcp ( x , a ) , min ( y - x , b - a ) ) ;
ans2 += b - a + 2 + count ( tmp ) - tmp ;
x = a , y = b ;
}
printf ( "%I64d %I64d
" , ans1 , ans2 ) ;
}
int main () {
while ( ~scanf ( "%s" , s ) ) solve () ;
return 0 ;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu4671(다교리그 7--수 시뮬레이션)클릭하여 링크 열기 제목: n과 서버, m개의 데이터베이스가 있고 모든 데이터베이스는 서버를 연결해야 하지만 모든 데이터베이스는 서버를 연결하는 우선순위가 있습니다.모든 데이터베이스의 서버 우선순위를 구하다.또한 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.