hdu 3518 (접미사 배열)
26268 단어 접미사 배열
code:
접미사 배열 처리, height 를 찾 습 니 다... 블 로 거들 의 상세 한 코드 사고방식 참고
1 #include<iostream>
2 #include<string>
3 using namespace std;
4 #define N 1200
5 string s;
6 int n, sa[4*N], rank[N], height[N];
7 int buf[4*N], ct[N], sx[N], sax[N];
8 inline bool leq(int a, int b, int x, int y)
9 {
10 return (a < x || a == x && b <= y);
11 }
12 inline bool leq(int a, int b, int c, int x, int y, int z)
13 {
14 return (a < x || a == x && leq(b, c, y, z));
15 }
16 inline int geti(int t, int nx, int sa[])
17 {
18 return (sa[t]<nx ? sa[t]*3+1 : (sa[t]-nx)*3+2);
19 }
20 //
21 static void radix(int a[], int b[], int s[], int n, int k)
22 { // sort a[0..n-1] to b[0..n-1] with keys in 0..k from s
23 int i, t, sum;
24 memset(ct, 0, (k + 1) * sizeof(int));
25 for (i = 0; i < n; ++i) ct[s[a[i]]]++;
26 for (i = 0, sum = 0; i <= k; ++i)
27 {
28 t = ct[i]; ct[i] = sum; sum += t;
29 }
30 for (i = 0; i < n; i++) b[ct[s[a[i]]]++] = a[i];
31 }
32
33 /*
34 , O(nlogn)。
35 ：
36 int *r： r ， r[0] r[n-1] ， n ， m 。
37 ， r[n-1] r[i] 0, r[n-1]=0 。
38 int *sa： ， sa ， sa[0] sa[n-1] 。
39 */
40 void suffix(int s[], int sa[], int n, int k)
41 { // !!! require s[n] = s[n+1] = s[n+2] = 0, n >= 2.
42 int i, j, e, p, t;
43 int name = 0, cx = -1, cy = -1, cz = -1;
44 int nx = (n+2)/3, ny = (n+1)/3, nz = n/3, nxz = nx+nz;
45 int *syz = s + n + 3, *sayz = sa + n + 3;
46 for (i=0, j=0; i < n + (nx - ny); i++)
47 if (i%3 != 0) syz[j++] = i;
48 radix(syz , sayz, s+2, nxz, k);
49 radix(sayz, syz , s+1, nxz, k);
50 radix(syz , sayz, s , nxz, k);
51 for (i = 0; i < nxz; i++)
52 {
53 if (s[ sayz[i] ] != cx || s[ sayz[i] + 1 ] != cy ||s[ sayz[i] + 2 ] != cz)
54 {
55 name++; cx = s[ sayz[i] ];
56 cy = s[ sayz[i] + 1 ]; cz = s[ sayz[i] + 2 ];
57 }
58 if (sayz[i] % 3 == 1) syz[ sayz[i] / 3 ] = name;
59 else syz[ sayz[i]/3 + nx ] = name;
60 }
61 if (name < nxz)
62 {
63 suffix(syz, sayz, nxz, name);
64 for (i = 0; i < nxz; i++) syz[sayz[i]] = i + 1;
65 }
66 else
67 {
68 for (i = 0; i < nxz; i++) sayz[syz[i] - 1] = i;
69 }
70 for (i = j = 0; i < nxz; i++)
71 if (sayz[i] < nx) sx[j++] = 3 * sayz[i];
72 radix(sx, sax, s, nx, k);
73 for (p=0, t=nx-ny, e=0; e < n; e++)
74 {
75 i = geti(t, nx, sayz); j = sax[p];
76 if ( sayz[t] < nx ?leq(s[i], syz[sayz[t]+nx], s[j], syz[j/3]) :
77 leq(s[i], s[i+1], syz[sayz[t]-nx+1],
78 s[j], s[j+1], syz[j/3+nx]) )
79 {
80 sa[e] = i;
81 if (++t == nxz)
82 {
83 for (e++; p < nx; p++, e++)
84 sa[e] = sax[p];
85 }
86 }
87 else
88 {
89 sa[e] = j;
90 if (++p == nx) for (++e; t < nxz; ++t, ++e)
91 sa[e] = geti(t, nx, sayz);
92 }
93 }
94 }
95
96 /*
97 SA ， 1..n SA[1]，SA[2]，……，SA[n]，
98 Suffix(SA[i]) < Suffix(SA[i+1]) ， 1 ≤ i<n 。
99 S n SA 。
100 */
101 void makesa()
102 {
103 memset(buf, 0, 4 * n * sizeof(int));
104 memset(sa, 0, 4 * n * sizeof(int));
105 for (int i=0; i<n; ++i) buf[i] = s[i] & 0xff;
106 suffix(buf, sa, n, 255);
107 }
108
109
110
111 /*
112 Rank[i] Suffix(i) “ ” 。
113 ， 。
114 n 。
115 ， ， ， 。
116 ， O(1) 。
117 ， O(n) 。
118 ， n ， n “ ” 。
119 */
120 void getRank()
121 {
122 for(int i = 1;i < n; ++ i)
123 rank[sa[i]] = i;
124 }
125 /*
126 u,v lcp(u,v)=max{i|u=iv}， u v ， ，
127 。
128 i,j LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j]))， i,j 1 n 。LCP(i,j) i
129 j 。
130 height， height[i]=LCP(i-1,i)，1<i≤n， height[1]=0。
131 */
132 void lcp()
133 { // O(4 * N)
134 int i, j, k;
135 for (j = rank[height[i=k=0]=0]; i < n - 1; i++, k++)
136 while (k >= 0 && s[i] != s[ sa[j-1] + k ])
137 height[j] = (k--), j = rank[ sa[j] + 1 ];
138 }
139 int main()
140 {
141
142 while(cin>>s && s[0] != '#')
143 {
144 n = s.length() + 1;
145 makesa();
146 getRank();
147 lcp();
148 int ans = 0, minid, maxid;
149 // h
150 for(int i = 1; i <= (n >> 1); i++)
151 {
152 minid = 1200, maxid = -1;
153 // h， height ， height h l r。
154 for(int j = 2; j < n; j++)
155 if (height[j] >= i)
156 {
157 if (sa[j - 1] < minid) minid = sa[j - 1];
158 if (sa[j - 1] > maxid) maxid = sa[j - 1];
159 if (sa[j] < minid) minid = sa[j];
160 if (sa[j] > maxid) maxid = sa[j];
161 }
162 else
163 {
164 // l + h - 1 < r ， ， 1.
165 if (maxid != -1 && minid + i <= maxid) ans++;
166 minid = 1200, maxid = -1;
167 }
168 // l + h - 1 < r ， ， 1.
169 if (maxid != -1 && minid + i <= maxid) ans++;
170 }
171 cout<<ans<<endl;
172 }
173 return 0;
174 }좋은 웹페이지 즐겨찾기
