處理字符串的有力武器。。。
理論就不多講了，
我的實現：
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 *x = rk, *y = 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