首页 > 代码库 > hdu 5008

hdu 5008

2024-08-02 20:05:20   215人阅读

题目是要求一个字符串中第k小的子串 ， 如果想到一个子串必定是一个后缀的前缀 ， 那么就可以用后缀数组来解决了 ， 后缀数组记录着有序的所有后缀 ， 而且每个后缀的不重复的子串数是确定的 ， 就是n-sa[i]-height[i] ， 如果不理解这个公式， 可以自己对照所有后缀去用笔画 ， 既然这个确定了， 那么很自然的就能知道 ，可以维护一个记录着每个后缀的子串的数目的数组 ， 然后二分找到k小子串对应的后缀 ， 接着就是细节处理 ， 每次都往后去找l最小的子串 。

 

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5   6 const int N = 200100 ;  7   8 using namespace std ;  9  10 char str[N]; 11 int sa[N] , rank[N] , height[N] , n , t1[N] , t2[N] , c[N] , l , r; 12 long long num[N] ; 13  14 void build_sa( int m ) 15 { 16      int *x = t1 , *y = t2 ; 17       18      for( int i=0;i<m;i++ ) c[i] = 0 ; 19       20      for( int i=0;i<n;i++ ) c[ x[i]=str[i] ] ++ ; 21       22      for( int i=1;i<m;i++ ) c[i] += c[i-1] ; 23       24      for( int i=n-1;i>=0;i-- ) sa[ --c[ x[i] ] ] = i ; 25       26      for( int k=1;k<=n;k<<=1 ){ 27               int p = 0 ; 28                29               for( int i=n-k;i<n;i++ ) y[p++] = i ; 30                31               for( int i=0;i<n;i++ ) if( sa[i]>=k ) y[p++] = sa[i] - k ; 32                33               for( int i=0;i<m;i++ ) c[i] = 0 ; 34                35               for( int i=0;i<n;i++ ) c[ x[y[i]] ] ++ ; 36                37               for( int i=1;i<m;i++ ) c[i] += c[i-1] ; 38                39               for( int i=n-1;i>=0;i-- ) sa[ --c[ x[y[i]] ] ] = y[i] ; 40                41               swap( x , y ) ; 42                43               p = 1 ; x[ sa[0] ] = 0 ; 44                45               for( int i=1;i<n;i++ ) 46                        x[ sa[i] ] = y[ sa[i-1] ]==y[ sa[i] ] && y[ sa[i-1]+k ]==y[ sa[i]+k ] ? p-1 : p++ ; 47                         48               if( p>=n ) break ; 49                50               m = p ;        51      } 52 } 53  54 void get_height() 55 { 56      for( int i=0;i<n;i++ ) rank[ sa[i] ] = i ; 57       58      int k = 0 ; 59       60      for( int i=0;i<n;i++ ){ 61               if( k ) k-- ; 62                63               int j = sa[ rank[i]-1 ] ; 64                65               while( str[i+k]==str[j+k] ) k ++ ; 66                67               height[ rank[i] ] = k ;      68      } 69       70      height[n] = 0 ;  71 } 72  73 void build_num() 74 { 75      num[0] = 0 ; 76      height[1] = 0 ;  77      for( int i=1;i<n;i++ ){ 78               num[i] = n-1-sa[i] - height[i] + num[i-1] ; 79      }      80      height[n] = 0 ;         81 } 82  83 int main() 84 { 85      while( scanf("%s" , str)!=EOF ) 86      { 87             int q ; 88             long long x , v; 89       90             n = strlen(str); 91              92             str[n] = ‘a‘ - 1 ; 93              94             n++ ; 95              96             l = r = 0 ; 97              98             build_sa(127) ;  get_height();//求后缀数组 
99            100             build_num();//这里就是求出已经排好序的每个后缀的子串数， 并且维护前缀和   
101        102             scanf("%d" , &q);103              104             while( q-- ){105                    106                    scanf("%I64d", &v);  107                         108                    x = (long long)( (l^r^v) + 1ll ) ;109                    110                    if( x>num[n-1] ){111                              l = r = 0 ;112                              printf("%d %d\n" , l , r) ; 113                              continue ;   114                    }115                    116                    int k1 = lower_bound( num+1 , num+n , x ) - num ;117                    118                    x -= num[k1-1] ;119                    120                    int len = height[k1] + x , ind = k1 , Min = sa[ind] ; 121                    122                    while( ind<n-1 && height[ind+1]>=len ){123                                   ind ++ ;   124                                   Min = min( Min , sa[ind] ) ;125                    }126                    127                    l = Min ;128                    r = l + len -1 ;129                    l++ ; r++ ;130                    131                    printf("%d %d\n" , l , r);132                    133             }134      }135 }

 

hdu 5008


联系
我们