倍增算法N(lgN)^2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| /************************************************************** Problem: 1031 User: mudream4869 Language: C++ Result: Accepted Time:1296 ms Memory:3544 kb****************************************************************/#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>using namespace std;void dump(int n, int* arr){ for(int lx = 0;lx < n;lx++) printf("%d ", arr[lx]); puts(""); return;}char buf[200010], ret[200010];int rnk[2][200000];int sa[200000];struct CMP{ int* rk; int n, len; bool operator()(const int& i, const int& j){ if(rk[i] != rk[j]) return rk[i] < rk[j]; int a = (i+n < len) ? rk[i+n] : -1; int b = (j+n < len) ? rk[j+n] : -1; return a < b; }};void build_sa(){ int len = strlen(buf); int now = 0; for(int lx = 0;lx < len;lx++) rnk[0][lx] = buf[lx]; for(int lx = 0;lx < len;lx++) sa[lx] = lx; for(int l = 2; l <= len;l<<=1){ CMP cmp = {rnk[now], l>>1, len}; sort(sa, sa+len, cmp); rnk[now^1][sa[0]] = 0; for(int lx = 1;lx < len;lx++) rnk[now^1][sa[lx]] = rnk[now^1][sa[lx-1]] + cmp(sa[lx-1], sa[lx]); now ^= 1; } return;}int main(){ scanf("%s", buf); int len = strlen(buf); for(int lx = len;lx>=0;lx--) buf[lx+len] = buf[lx]; build_sa(); for(int lx = 0;lx < 2*len;lx++){ if(sa[lx] >= len) continue; printf("%c", buf[sa[lx]+len-1]); } puts(""); return 0;} |
沒有留言:
張貼留言