首页 > 代码库 > LA 4513
LA 4513
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2514、
此题需要求在一个字符串中出现至少k次的最长子串， 如果有多个， 取rightmost的那个 ， 还是用后缀数组 ， 二分然后分段处理 ， 不过也可以用hash解决 ， 这里先给出后缀数组的代码 。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 7 const int N = 44444 ; 8 9 using namespace std ; 10 11 char str[N] ; 12 int sa[N] , n , rank[N] , height[N] , t1[N] , t2[N] , c[N] , k; 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 p = 1 ; swap( x , y ) ; 42 43 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 /* for( int i=1;i<n;i++ ){ 73 for( int j=sa[i];j<n-1;j++ ) 74 cout<<str[j]<<" "; 75 cout<<endl; 76 }*/ 77 } 78 79 bool is_ok( int mid ) 80 { 81 int pre = 1 ; 82 83 for( int i=2;i<=n;i++ ){ 84 if( height[i]<mid ){ 85 if( i-pre>=k ) return true ; 86 pre = i ; 87 } 88 } 89 90 return false ; 91 } 92 93 void print( int mid ) 94 { 95 int pre = 1 , Max = 0 ; 96 97 for( int i=2;i<=n;i++ ){ 98 if( height[i]<mid ){ 99 if( i-pre>=k && height[i-1]>=mid ){ 100 for( int j=pre;j<i;j++ )101 Max = max( Max , sa[j] ) ;102 } 103 pre = i ; 104 } 105 }106 107 printf("%d %d\n" , mid , Max);108 }109 110 int main()111 {112 while( scanf("%d" , &k)!=EOF && k )113 {114 scanf("%s" , str) ;115 116 n = strlen(str) ;117 118 str[n] = ‘a‘ - 1 ;119 120 n++ ;121 122 build_sa(127) ; get_height() ;123 124 int l = 0 , r = n-1 ;125 126 while( l<r ){127 if( l==r-1 ) break ; 128 129 int mid = ( l+r ) >> 1 ;130 131 if( is_ok(mid)==true )132 l = mid ;133 else r = mid - 1 ; 134 }135 136 if( is_ok(r)==true ) print(r) ;137 else if( l==0 ) printf("none\n");138 else print(l) ;139 }140 }
LA 4513
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。