首页 > 代码库 > poj 3294
poj 3294
一道非常经典的题目 ， 求至少在超过一半的字符串中出现过的最长子串 ， 并且按字典序删除 ， 方法有很多种 ， 后缀数组也可以 ， 在绝大多数的后缀数组题目中 ， 都要用到二分和分段的思想 ，二分长度，然后依据长度k分段 ， 分段即把height数组分成多段 ， 使得每一段中 ， 如果有多个字符串， 那么它们的公共前缀长度至少为k ， k就是在那里分段的依据 。 然后对于每一段 ， 因为其中字符串的公共前缀长度至少为k ， 满足二分的长度， 所以就只需要判断这些后缀来自的字符串的个数是否超过n/2即可。 如果不理解的话， 就自己对照程序，在纸上走几次。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<string> 6 #include<cmath> 7 8 const int N = 222222 ; 9 10 using namespace std ; 11 12 char Str[N] , s[1010] ; 13 int sa[N] , rank[N] , height[N] , t1[N] , t2[N] , c[N] , n , t_n; 14 int s_len[110] , str[N]; 15 bool flag[110] ; 16 17 void build_sa( int m ) 18 { 19 int *x = t1 , *y = t2 ; 20 21 for( int i=0;i<m;i++ ) c[i] = 0 ; 22 23 for( int i=0;i<n;i++ ) c[ x[i]=str[i] ] ++ ; 24 25 for( int i=1;i<m;i++ ) c[i] += c[i-1] ; 26 27 for( int i=n-1;i>=0;i-- ) sa[ --c[ x[i] ] ] = i ; 28 29 for( int k=1;k<=n;k<<=1 ){ 30 int p = 0 ; 31 32 for( int i=n-k;i<n;i++ ) y[p++] = i ; 33 34 for( int i=0;i<n;i++ ) if( sa[i]>=k ) y[p++] = sa[i] - k ; 35 36 for( int i=0;i<m;i++ ) c[i] = 0 ; 37 38 for( int i=0;i<n;i++ ) c[ x[y[i]] ] ++ ; 39 40 for( int i=1;i<m;i++ ) c[i] += c[i-1] ; 41 42 for( int i=n-1;i>=0;i-- ) sa[ --c[ x[y[i]] ] ] = y[i] ; 43 44 swap( x , y ); 45 46 p = 1 ; x[ sa[0] ] = 0 ; 47 48 for( int i=1;i<n;i++ ) 49 x[ sa[i] ] = y[ sa[i-1] ]==y[ sa[i] ] && y[ sa[i-1]+k ]==y[ sa[i]+k ] ? p-1 : p++ ; 50 51 if( p>=n ) break ; 52 53 m = p ; 54 } 55 } 56 57 void get_height() 58 { 59 for( int i=0;i<n;i++ ) rank[ sa[i] ] = i ; 60 61 int k = 0 ; 62 63 for( int i=0;i<n;i++ ){ 64 if( k ) k-- ; 65 66 int j = sa[ rank[i]-1 ] ; 67 68 while( str[i+k]==str[j+k] ) k++ ; 69 70 height[ rank[i] ] = k ; 71 } 72 } 73 74 int get( int x ) 75 { 76 x++ ; 77 for( int i=1;i<=t_n;i++ ){ 78 79 x -= s_len[i] ; 80 81 x-- ; 82 83 if( x<0 ) return i ; 84 if( x==0 ) return 0 ; 85 } 86 return 0 ; 87 } 88 89 bool is_ok( int mid ) 90 { 91 int pre = 1 ; 92 // cout<<mid<<endl; 93 for( int i=2;i<n;i++ ){ 94 if( height[i]<mid ){ 95 if( height[i-1]>=mid ){ 96 97 memset( flag , false , sizeof(flag) ); 98 for( int j=pre;j<i;j++ ){ 99 flag[ get( sa[j] ) ] = true ; 100 } 101 int num = 0 ; 102 for( int j=1;j<=t_n;j++ )103 if( flag[j]==true ) num ++ ;104 105 // cout<<num<<" num "<<" "<<endl;106 if( num>t_n/2 ) return true ;107 }108 pre = i; 109 }110 }111 return false ;112 }113 114 void print( int mid )115 {116 int pre = 1 ;117 118 for( int i=2;i<n;i++ ){119 120 if( height[i]<mid ){121 if( height[i-1]>=mid ){122 123 memset( flag , false , sizeof(flag) );124 for( int j=pre;j<i;j++ ){125 flag[ get( sa[j] ) ] = true ; 126 } 127 int num = 0 ; 128 for( int j=1;j<=t_n;j++ )129 if( flag[j]==true ) num ++ ;130 131 if( num>t_n/2 ){132 for( int k=0;k<mid && sa[pre]+k<n-1;k++ ) printf("%c" , (char)str[ sa[pre]+k ] ); 133 printf("\n");134 }135 }136 pre= i ;137 } 138 } 139 }140 141 int main()142 {143 int jishi = 0 ;144 145 while( scanf("%d" , &t_n)!=EOF && t_n )146 {147 if( jishi ) printf("\n");148 jishi ++ ;149 scanf("%s" , Str);150 151 n = strlen(Str) ;152 153 for( int i=0;i<n;i++ )154 str[i] = (int)Str[i] ;155 n-- ;156 157 s_len[1] = n+1 ;158 159 int t = 1 , len ;160 for( int i=2;i<=t_n;i++ ){161 scanf("%s" , s);162 163 len = strlen(s);164 s_len[++t] = len ;165 166 str[++n] = 127 + i ; 167 for( int j=0;j<len;j++ )168 str[++n] = s[j] ; 169 } 170 171 str[++n] = ‘a‘ - 2 ;172 173 n++ ;174 175 build_sa(350) ;176 177 get_height() ;178 179 int l = 0 , r = n , mid ;180 181 while( l<r ){182 if( l==r-1 ) break ; 183 mid = ( l+r ) >> 1 ;184 185 if( is_ok(mid)==true )186 l = mid ;187 else r = mid - 1 ; 188 }189 if( is_ok(r)==true ) print(r);190 else if( l==0 ) printf("?\n");191 else print(l); 192 }193 }
poj 3294
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。