coreBugZJ

此 blog 已弃。

后缀数组

处理字符串的有力武器。。。

理论就不多讲了,

我的实现:


  1 // txt[ 0..n ), txt[ 0..n-1 ] > 0, txt[ n ] == 0
  2 
  3 // sa[ 1..n ] = [ 0..n-1 ], sa[ 0 ] = n
  4 
  5 // rk[ 0..n-1 ] = [ 1..n ], rk[ n ] = 0
  6 
  7 
  8 
  9 void Da( const unsigned int * txt, int * pn, int * sa, int * rk, int * ht, int * tot, int totSize ) {
 10 
 11         int *= rk, *= ht, *txy, lastRk = totSize - 1, i, j, len, n;
 12 
 13 
 14 
 15         for( i = 0; i <= lastRk; ++i ){
 16 
 17                 tot[ i ] = 0;
 18 
 19         }
 20 
 21         for( n = 0; txt[ n ]; ++n ){
 22 
 23                 ++tot[ txt[ n ] ];
 24 
 25         }
 26 
 27         ++tot[ txt[ *pn = n ] ];
 28 
 29         for( i = 1; i <= lastRk; ++i ){
 30 
 31                 tot[ i ] += tot[ i - 1 ];
 32 
 33         }
 34 
 35         for( i = n; i >= 0--i ){
 36 
 37                 sa[ --tot[ txt[ i ] ] ] = i;
 38 
 39         }
 40 
 41         x[ sa[ 0 ] ] = lastRk = 0;
 42 
 43         for( i = 1; i <= n; ++i ){
 44 
 45                 if( txt[ sa[ i - 1 ] ] != txt[ sa[ i ] ] ){
 46 
 47                         ++lastRk;
 48 
 49                 }
 50 
 51                 x[ sa[ i ] ] = lastRk;
 52 
 53         }
 54 
 55 
 56 
 57         for( len = 1; lastRk < n; len <<= 1 ){
 58 
 59                 j = -1;
 60 
 61                 for( i = n - len + 1; i <= n; ++i ){
 62 
 63                         y[ ++j ] = i;
 64 
 65                 }
 66 
 67                 for( i = 0; i <= n; ++i ){
 68 
 69                         if( sa[ i ] >= len ){
 70 
 71                                 y[ ++j ] = sa[ i ] - len;
 72 
 73                         }
 74 
 75                 }
 76 
 77 
 78 
 79                 for( i = 0; i <= lastRk; ++i ){
 80 
 81                         tot[ i ] = 0;
 82 
 83                 }
 84 
 85                 for( i = 0; i <= n; ++i ){
 86 
 87                         ++tot[ x[ y[ i ] ] ];
 88 
 89                 }
 90 
 91                 for( i = 1; i <= lastRk; ++i ){
 92 
 93                         tot[ i ] += tot[ i - 1 ];
 94 
 95                 }
 96 
 97                 for( i = n; i >= 0--i ){
 98 
 99                         sa[ --tot[ x[ y[ i ] ] ] ] = y[ i ];
100 
101                 }
102 
103 
104 
105                 txy = x;
106 
107                 x   = y;
108 
109                 y   = txy;
110 
111                 x[ sa[ 0 ] ] = lastRk = 0;
112 
113                 for( i = 1; i <= n; ++i ){
114 
115                         x[ sa[ i ] ] = ( ( y[ sa[ i - 1 ] ] == y[ sa[ i ] ] ) && 
116 
117                                          ( y[ sa[ i - 1 ] + len ] == y[ sa[ i ] + len ] )
118 
119                                        ) ? lastRk : ++lastRk;
120 
121                 }
122 
123         }
124 
125 
126 
127         for( i = 0; i <= n; ++i ){
128 
129                 rk[ i ] = x[ i ];
130 
131         }
132 
133 
134 
135         for( ht[ 0 ] = len = i = 0; i < n; ++i ){
136 
137                 if( len > 0 ){
138 
139                         --len;
140 
141                 }
142 
143                 j = sa[ rk[ i ] - 1 ];
144 
145                 while( txt[ i + len ] == txt[ j + len ] ){
146 
147                         ++len;
148 
149                 }
150 
151                 ht[ rk[ i ] ] = len;
152 
153         }
154 
155         return;
156 
157 }
158 


posted on 2011-03-20 19:12 coreBugZJ 阅读(1246) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理