给你一个字符串，然后询问它第k小的factor，坑的地方在于spoj实在是太慢了，要加各种常数优化，字符集如果不压缩一下必t。。
|
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110 |
#pragma warning(disable:4996)#include<cstring>#include<string>#include<iostream>#include<cmath>#include<vector>#include<algorithm>#define maxn 90050using
namespace std;struct
State{ State *suf, *go[26]; int
val, cnt; char
transch; State() :suf(0), val(0){ memset(go, 0, sizeof(go)); }}*root, *last;State statePool[maxn * 2], *cur;void
init(){ cur = statePool; root = last = cur++;}void
extend(int
w){ State *p = last, *np = cur++; np->val = p->val + 1; np->cnt = 1; while
(p&&!p->go[w]) p->go[w] = np, p = p->suf; if
(!p) np->suf = root; else{ State *q = p->go[w]; if
(p->val + 1 == q->val){ np->suf = q; } else{ State *nq = cur++; memcpy(nq->go, q->go, sizeof
q->go); nq->val = p->val + 1; nq->cnt = 1; nq->suf = q->suf; q->suf = nq; np->suf = nq; while
(p&&p->go[w] == q){ p->go[w] = nq, p = p->suf; } } } last = np;}char
str[maxn];char
ans[maxn];int
atop;int
n;int
q;int
bcnt[maxn];State *b[maxn * 2];int
main(){ scanf("%s", str); n = strlen(str); init(); for
(int i = 0; i < n; i++){ extend(str[i] - ‘a‘); } int
tot = cur - statePool; for
(int i = 0; i < tot; i++) bcnt[statePool[i].val]++; for
(int i = 1; i <= n; i++) bcnt[i] += bcnt[i - 1]; for
(int i = 0; i < tot; i++) b[--bcnt[statePool[i].val]] = statePool + i; for
(int i = tot - 1; i >= 0; i--){ int
kth = 0; State *p = b[i]; for
(int j = 0; j < 26; j++){ if
(p->go[j]){ p->cnt += p->go[j]->cnt; p->go[kth++] = p->go[j]; p->go[j]->transch = ‘a‘
+ j; } } p->go[kth] = NULL; } scanf("%d", &q); int
k; while
(q--) { scanf("%d", &k); State *p = root; atop = 0; while
(k){ for
(int x = 0; p->go[x]; x++){ if
(k > p->go[x]->cnt) k -= p->go[x]->cnt; else
{ k -= 1; p = p->go[x]; ans[atop++] = p->transch; break; } } } ans[atop] = ‘\0‘; puts(ans); } return
0;} |
SPOJ Lexicographical Substring Search 后缀自动机
原文：http://www.cnblogs.com/chanme/p/3551952.html