江苏信安竞赛初赛工作组记事

11月21日,比赛前一天

20日晚还在赶第二天编译原理课的展示,21日上午才开始搞江苏信安竞赛初赛的运维。网站还没有用户和队伍信息,信息要从一个csv文件中导入。也没有题目信息,需要从一个.docx文件里导入,我用的办法是unoconv -f txt a.docx转成文本文件a.txt后用awk处理得到csv格式的文件,之后在Rails项目的lib/tasks目录里创建了一个导入csv格式题目信息的task。在BCTF初赛平台的基础上,还有很多页面、路由和模型等需要调整。

Read More

Hackerrank FP Compilers题目

Generate String from Regex

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
111
112
113
114
115
let is_lower c =
'a' <= c && c <= 'z'

type ast =
| Lit of char
| Star of ast
| Cat of ast*ast
| Or of ast*ast

module Parser = struct
type state = Ret of ast | Cont of char list * ast list

let parse re =
let isp_tbl = Hashtbl.create 10 in
let icp_tbl = Hashtbl.create 10 in
List.iter (fun (c,x) -> Hashtbl.replace isp_tbl c x)
['\x00',0; '(',1; '|',3; '%',5; '*',7; ')',7];
List.iter (fun (c,x) -> Hashtbl.replace icp_tbl c x)
['\x00',0; ')',1; '|',2; '%',4; '*',6; '(',6];

let n = String.length re in
let rec go ops vs i =
let implicit_cat = 0 < i && i < n && (re.[i] = '(' || is_lower re.[i]) &&
(re.[i-1] <> '(' && re.[i-1] <> '|') in
let incoming implicit_cat ops vs =
let ic = if implicit_cat then '%' else if i = n then '\x00' else re.[i] in
if is_lower ic then
Cont (ops, Lit ic::vs)
else
let icp = Hashtbl.find icp_tbl ic in
let rec pop_go (op::ops' as ops) vs =
if Hashtbl.find isp_tbl op > icp then
match op with
| '*' ->
let x::vs' = vs in
pop_go ops' (Star x::vs')
| '%' ->
let y::x::vs' = vs in
pop_go ops' (Cat (x,y)::vs')
| '|' ->
let y::x::vs' = vs in
pop_go ops' (Or (x,y)::vs')
| c ->
Printf.printf "+ c: %c %c\n" op ic;
ops ,vs
else
ops, vs
in
let (op::ops' as ops), vs = pop_go ops vs in
if Hashtbl.find isp_tbl op = icp then (
if ic = '\x00' then
Ret (List.hd vs)
else
Cont (ops', vs)
) else
Cont (ic::ops, vs)
in
match incoming implicit_cat ops vs with
| Ret _ as ret -> ret
| Cont (ops,vs) ->
if not implicit_cat then
go ops vs (i+1)
else
let Cont (ops,vs) = incoming false ops vs in
go ops vs (i+1)
in
let Ret ret = go ['\x00'] [] 0 in
ret
end

let generate len =
let rec go = function
| Lit lit ->
let a = Array.make (len+1) "#" in
a.(1) <- String.make 1 lit;
a
| Star x ->
let b = go x in
let a = Array.make (len+1) "#" in
a.(0) <- "";
for i = 1 to len do
let rec fill j =
if j > 0 then
if b.(j) <> "#" && a.(i-j) <> "#" then
a.(i) <- a.(i-j) ^ b.(j)
else
fill (j-1)
in
fill i
done;
a
| Cat (x,y) ->
let b = go x and c = go y in
let a = Array.make (len+1) "#" in
for i = 0 to len do
for j = 0 to len-i do
if a.(i+j) = "#" && b.(i) <> "#" && c.(j) <> "#" then
a.(i+j) <- b.(i) ^ c.(j)
done
done;
a
| Or (x,y) ->
let b = go x in
let c = go y in
Array.init (len+1) (fun i -> if b.(i) <> "#" then b.(i) else c.(i))
in
go

let () =
let len = read_int () in
let re = read_line () in
let ast = Parser.parse re in
let a = generate len ast in
let s = a.(len) in
print_endline (if s <> "#" then s else "NIL")

While Language

生成AST后进入求值阶段,可以用state monad处理求值部分。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
module Str = struct
let implode l =
let s = String.make (List.length l) ' ' in
let rec go i = function
| [] -> s
| h::t -> s.[i] <- h; go (i+1) t
in
go 0 l

let explode s =
let rec go acc i =
if i = String.length s then
List.rev acc
else
go (s.[i]::acc) (i+1)
in
go [] 0
end

module LazyList = struct
type 'a node = Nil | Cons of 'a * 'a t and 'a t = 'a node Lazy.t
let empty = lazy Nil
let singleton x = lazy (Cons (x, empty))
let cons h t = lazy (Cons (h, t))
let force = Lazy.force
let rec map f l = lazy (
match force l with
| Nil -> Nil
| Cons (h, t) -> Cons (f h, map f t)
)
let rec append l1 l2 = lazy (
match force l1 with
| Nil -> force l2
| Cons (h, t) -> Cons (h, append t l2)
)
let rec concat ll = lazy (
match force ll with
| Nil -> Nil
| Cons (h, t) -> append h (concat t) |> force
)
let is_empty l =
match force l with
| Nil -> true
| Cons _ -> false
end

module ParserCombinators = struct
type input = { s: string; pos: int }
type 'a t = input -> ('a * input) LazyList.node Lazy.t

let unit x s = LazyList.singleton (x, s)
let zero = unit []
let (>>=) (type a) (type b) (x : a t) (f : a -> b t) s = LazyList.map (fun (a,s') -> f a s') (x s) |> LazyList.concat
let (>>) x y = x >>= fun _ -> y
let (<<) x y = x >>= fun b -> y >> unit b
let (<|>) x y s = let r = x s in if LazyList.is_empty r then y s else r
let fail s = LazyList.empty
let (<$>) f x = x >>= fun b -> unit (f b)
let (<$) b x = x >> unit b
let (<*>) f x = f >>= fun g -> x >>= fun b -> unit (g b)
let (<**>) x f = x >>= fun b -> f >>= fun g -> unit (g b)

let rec many x =
let go = x >>= fun b ->
many x >>= fun bs ->
unit (b::bs)
in
go <|> zero

let many1 x =
x >>= fun b ->
many x >>= fun bs ->
unit (b::bs)

let next s =
if s.pos = String.length s.s then
None
else
Some (s.s.[s.pos], { s with pos = s.pos + 1 })

let pred f = (fun s -> match next s with
| None -> LazyList.empty
| Some x -> LazyList.singleton x) >>= fun b ->
if f b then unit b else fail

let char c = pred (fun c' -> c = c')
let str s =
let rec go = function
| [] -> zero
| h::t -> char h >>= fun b -> go t >>= fun bs -> unit (b::bs)
in
Str.explode s |> go
let digit = pred (fun c -> '0' <= c && c <= '9')
let lower = pred (fun c -> 'a' <= c && c <= 'z')
let drop x = x >> zero
let space = pred (fun c -> c = ' ' || c = '\t' || c = '\r' || c = '\n')
let token x = x << drop (many space)
let char_ c = char c |> token
let str_ s = str s |> token

let sep_by x sep =
let go = x >>= fun b ->
many (drop sep >> x) >>= fun bs ->
unit (b::bs)
in
go <|> zero

let chainl1 x op =
let rec go a =
(op >>= fun f ->
x >>= fun b ->
go (f a b)) <|> unit a
in
x >>= go

let parse x s =
match LazyList.force ((drop (many space) >> x) { s; pos = 0 }) with
| LazyList.Nil -> None
| LazyList.Cons ((x, _), _) -> Some x
end

type aexpr =
| Num of int64
| Var of string
| Add of aexpr * aexpr
| Sub of aexpr * aexpr
| Mul of aexpr * aexpr
| Div of aexpr * aexpr

type bexpr =
| Bool of bool
| Not of bexpr
| And of bexpr * bexpr
| Or of bexpr * bexpr
| Lt of aexpr * aexpr
| Gt of aexpr * aexpr

type stmt =
| Chain of stmt list
| Assign of string * aexpr
| If of bexpr * stmt * stmt
| While of bexpr * stmt

module Parser = struct
include ParserCombinators

let add x y = Add (x,y)
let sub x y = Sub (x,y)
let mul x y = Mul (x,y)
let div x y = Div (x,y)
let num l = Num (Str.implode l |> Int64.of_string)
let var l = Var (Str.implode l)
let chain xs = Chain xs
let if_ b t e = If (b,t,e)
let while_ b t = While (b,t)
let assign x y = Assign (x,y)
let and_ x y = And (x,y)
let or_ x y = Or (x,y)
let lt x y = Lt (x,y)
let gt x y = Gt (x,y)

let rec aexpr =
let rec e0 = lazy ((num <$> token (many1 digit)) <|> (var <$> token (many1 lower)) <|> (fun s -> (char_ '(' >> Lazy.force e2 << char_ ')') s))
and e1 = lazy (chainl1 (Lazy.force e0) ((mul <$ char_ '*') <|> (div <$ char_ '/')))
and e2 = lazy (chainl1 (Lazy.force e1) ((add <$ char_ '+') <|> (sub <$ char_ '-')))
in
Lazy.force e2

let rec bexpr =
let rec e0 = lazy ((Bool false <$ str_ "false") <|> (Bool true <$ str_ "true") <|>
(fun s -> (char_ '(' >> Lazy.force e3 << char_ ')') s)
)
and e1 = lazy ((aexpr <**> ((lt <$ char_ '<') <|> (gt <$ char_ '>')) <*> aexpr) <|> Lazy.force e0)
and e2 = lazy (chainl1 (Lazy.force e1) ((and_ <$ str_ "and")))
and e3 = lazy (chainl1 (Lazy.force e2) ((or_ <$ str_ "or")))
in
Lazy.force e3

let rec stmt =
let rec sassign = lazy (Str.implode <$> token (many1 lower) <**> (assign <$ str_ ":=") <*> aexpr)
and sif = lazy ((if_ <$ str_ "if") <*> bexpr << str_ "then" <*> Lazy.force sb << str_ "else" <*> Lazy.force sb)
and sb = lazy (char_ '{' >> (fun s -> Lazy.force s1 s) << char_ '}')
and swhile = lazy ((while_ <$ str_ "while") <*> bexpr << str_ "do" <*> Lazy.force sb)
and s0 = lazy (Lazy.force sif <|> Lazy.force swhile <|> Lazy.force sb <|> Lazy.force sassign)
and s1 = lazy (chain <$> sep_by (Lazy.force s0) (char_ ';'))
in
Lazy.force s1
end

module Eval = struct
type store = (string, int64) Hashtbl.t
type 'a t = store -> 'a

let unit a s = a
let (>>=) x f s = f (x s) s
let (>>) x y = x >>= fun _ -> y
let (<$>) f x s = x s |> f
let rec map_ f = function
| [] -> unit ()
| h::t -> f h >> map_ f t
let liftM2 f x y s =
let x' = x s in
let y' = y s in
f x' y'

let rec eval_a = function
| Num n -> unit n
| Var v -> fun tbl -> Hashtbl.find tbl v
| Add (x,y) -> liftM2 Int64.add (eval_a x) (eval_a y)
| Sub (x,y) -> liftM2 Int64.sub (eval_a x) (eval_a y)
| Mul (x,y) -> liftM2 Int64.mul (eval_a x) (eval_a y)
| Div (x,y) -> liftM2 Int64.div (eval_a x) (eval_a y)

let rec eval_b = function
| Bool b -> unit b
| Not x -> not <$> eval_b x
| And (x,y) -> liftM2 (&&) (eval_b x) (eval_b y)
| Or (x,y) -> liftM2 (||) (eval_b x) (eval_b y)
| Lt (x,y) -> liftM2 (<) (eval_a x) (eval_a y)
| Gt (x,y) -> liftM2 (>) (eval_a x) (eval_a y)

let rec eval_s = function
| Assign (v,x) -> fun tbl -> Hashtbl.replace tbl v (eval_a x tbl)
| Chain xs -> map_ eval_s xs
| If (b,t,e) -> eval_b b >>= fun b' -> eval_s (if b' then t else e)
| While (b,t) as w -> eval_b b >>= fun b' -> if b' then eval_s t >> eval_s w else unit ()

let interpret ast =
let tbl = Hashtbl.create 13 in
eval_s ast tbl;
Hashtbl.fold (fun k v xs -> (k,v)::xs) tbl [] |> List.sort compare |> List.iter (fun (k,v) ->
Printf.printf "%s %Ld\n" k v
)
end

let read _ =
let rec go acc =
try
let s = read_line () in
go (s::acc)
with End_of_file ->
String.concat "\n" (List.rev acc)
in
go []

let () =
match Parser.parse Parser.stmt (read 0) with
| None -> ()
| Some ast -> Eval.interpret ast

Down With Abstractions

https://www.hackerrank.com/challenges/down-with-abstractions

要求把lambda calculus转化为SKIBC组合子,Wikipedia给出了一个算法进行这种转换。我尝试用De Bruijn index表示的lambda calculus实现。算法中有一个子程序是判断某个子calculus内是否有一个变量为free的,如果用朴素的实现方式(遍历取出所有变量,一一判断是否存在free的),会增大时间复杂度。如果calculus的形态不发生改变,那么可以Inversion of Control:对于每个lambda abstraction找自由变量的要求,转换为把所有变量涉及的lambda abstraction标记出来。考虑到算子的形态会发生改变,我最终采用对于每个子calculus设置一个persistent heap来表示。

下面是实现代码,其中还结合state monad和lazy list实现了一个parser monad,用parsing expression grammar的方式来处理。 mutually recursive函数,目前理解得尚不清楚,用了一个比较麻烦的方式tying-the-knot:各function都表示为lazy的,这样所有的引用都需要表示为Lazy.force referenced的形式,另外对于引用链上所有back reference的地方都要使用eta expansion。如果不这么做会报运行时错误。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
module Str = struct
let implode l =
let s = String.make (List.length l) ' ' in
let rec go i = function
| [] -> s
| h::t -> s.[i] <- h; go (i+1) t
in
go 0 l

let explode s =
let rec go acc i =
if i = String.length s then
List.rev acc
else
go (s.[i]::acc) (i+1)
in
go [] 0
end

module LazyList = struct
type 'a node = Nil | Cons of 'a * 'a t and 'a t = 'a node Lazy.t
let empty = lazy Nil
let singleton x = lazy (Cons (x, empty))
let cons h t = lazy (Cons (h, t))
let force = Lazy.force
let rec map f l = lazy (
match force l with
| Nil -> Nil
| Cons (h, t) -> Cons (f h, map f t)
)
let rec append l1 l2 = lazy (
match force l1 with
| Nil -> force l2
| Cons (h, t) -> Cons (h, append t l2)
)
let rec concat ll = lazy (
match force ll with
| Nil -> Nil
| Cons (h, t) -> append h (concat t) |> force
)
let is_empty l =
match force l with
| Nil -> true
| Cons _ -> false
end

module ParserCombinators(S : sig type store end) = struct
type store = S.store
type input = { s: string; pos: int; store: store }
type 'a t = input -> ('a * input) LazyList.node Lazy.t

let unit x s = LazyList.singleton (x, s)
let zero = unit []
let (>>=) (type a) (type b) (x : a t) (f : a -> b t) s = LazyList.map (fun (a,s') -> f a s') (x s) |> LazyList.concat
let (>>) x y = x >>= fun _ -> y
let (<<) x y = x >>= fun b -> y >> unit b
let (<|>) x y s = let r = x s in if LazyList.is_empty r then y s else r
let fail s = LazyList.empty
let (<$>) f x = x >>= fun b -> unit (f b)
let (<$) b x = x >> unit b
let (<*>) f x = f >>= fun g -> x >>= fun b -> unit (g b)
let (<**>) x f = x >>= fun b -> f >>= fun g -> unit (g b)

let rec many x =
let go = x >>= fun b ->
many x >>= fun bs ->
unit (b::bs)
in
go <|> zero

let many1 x =
x >>= fun b ->
many x >>= fun bs ->
unit (b::bs)

let next s =
if s.pos = String.length s.s then
None
else
Some (s.s.[s.pos], { s with pos = s.pos + 1 })

let pred f = (fun s -> match next s with
| None -> LazyList.empty
| Some x -> LazyList.singleton x) >>= fun b ->
if f b then unit b else fail

let char c = pred (fun c' -> c = c')
let str s =
let rec go = function
| [] -> zero
| h::t -> char h >>= fun b -> go t >>= fun bs -> unit (b::bs)
in
Str.explode s |> go
let drop x = x >> zero
let space = pred (fun c -> c = ' ' || c = '\t' || c = '\r' || c = '\n')
let ident = Str.implode <$> many1 (pred (fun c -> 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9' || c = '_'))

let token x = x << drop (many space)
let char_ c = char c |> token
let ident_ = token ident

let (>>::) x y =
x >>= fun a ->
y >>= fun b ->
unit (a::b)

let sep_by x sep =
let go = x >>= fun b ->
many (drop sep >> x) >>= fun bs ->
unit (b::bs)
in
go <|> zero

let chainl1 x op =
let rec go a =
(op >>= fun f ->
x >>= fun b ->
go (f a b)) <|> unit a
in
x >>= go

let rec chainr1 x op =
let go a =
(op >>= fun f ->
chainr1 x op >>= fun b ->
unit (f a b)) <|> unit a
in
x >>= go

let parse x store s =
match LazyList.force ((drop (many space) >> x) { s; pos = 0; store }) with
| LazyList.Nil -> None
| LazyList.Cons ((x, _), _) -> Some x
end

module LeftistHeap = struct
type t = E | N of int * int * int * t * t

let empty = E

let is_empty = function
| E -> true
| _ -> false

let singleton x = N (x,0,0,E,E)

let rank = function
| E -> -1
| N (_,_,rk,_,_) -> rk

let make x l r =
if rank l >= rank r then
N (x,0,rank r+1,l,r)
else
N (x,0,rank l+1,r,l)

let add i = function
| E -> E
| N (x,d,rk,l,r) -> N (x+i,d+i,rk,l,r)

let rec merge h1 h2 = match h1, h2 with
| E, _ -> h2
| _, E -> h1
| N (x,d1,_,l1,r1), N (y,d2,_,l2,r2) ->
if x < y then
make x (add d1 l1) (merge (add d1 r1) h2)
else
make y (add d2 l2) (merge (add d2 r2) h1)

let top = function
| E -> invalid_arg "empty"
| N (x,_,_,_,_) -> x

let pop = function
| E -> invalid_arg "empty"
| N (_,d,_,l,r) -> merge (add d l) (add d r)

let push h x = merge h (N (x,0,0,E,E))
end

type term =
| Var of LeftistHeap.t * int
| Abs of LeftistHeap.t * term
| App of LeftistHeap.t * term * term
| S
| K
| I
| B
| C

module List = struct
include List

let fold_left1 f xs =
List.fold_left f (List.hd xs) (List.tl xs)

let rec drop c = function
| [] -> []
| _::xs' as xs ->
if c = 0 then
xs
else
drop (c-1) xs'
end

let get_dh = function
| Var (dh,_) -> dh
| App (dh,_,_) -> dh
| Abs (dh,_) -> dh
| _ -> LeftistHeap.empty

let rec cut dh =
if LeftistHeap.is_empty dh then
dh
else if LeftistHeap.top dh < 0 then
cut (LeftistHeap.pop dh)
else
dh

(*let rec free l = function*)
(*| Var (dh, c) -> c = l*)
(*| App (dh,x,y) -> free l x || free l y*)
(*| Abs (dh,x) -> free (l+1) x*)
(*| _ -> false*)

let free x = match x with
| Var (_,_)
| App (_,_,_)
| Abs (_,_) ->
let dh = get_dh x in
not (LeftistHeap.is_empty dh) && LeftistHeap.top dh = 0
| _ -> false

let rec shift = function
| Var (dh,c) as v -> Var (LeftistHeap.add (-1) dh |> cut, c-1)
| App (dh,x,y) -> App (LeftistHeap.add (-1) dh |> cut, shift x, shift y)
| Abs _ -> assert false
| c -> c

let var x = Var (LeftistHeap.singleton x, x)

let abstract x = Abs (LeftistHeap.add (-1) (get_dh x) |> cut, x)

let app x y = App (LeftistHeap.merge (get_dh x) (get_dh y), x, y)

let rec nest lv t =
if lv = 0 then
t
else
nest (lv-1) (abstract t)

let print t =
let rec go r = function
| Var (_,c) ->
Printf.printf "%d" c
| Abs _ ->
assert false
| App (_,x,y) ->
if r then print_char '(';
go false x;
go true y;
if r then print_char ')'
| S -> print_char 'S'
| K -> print_char 'K'
| I -> print_char 'I'
| B -> print_char 'B'
| C -> print_char 'C'
in
go false t

let rec tr =
let e = LeftistHeap.empty in function
| App (_,x,y) -> app (tr x) (tr y)
| Abs (_, Var (_, 0)) -> I
| Abs (_, App (_, x, Var (_, 0))) when not (free x) ->
tr x |> shift
| Abs (_, x) ->
if not (free x) then
app K (tr x |> shift)
else (
match x with
| Abs (_, y) ->
tr (abstract (tr x))
| App (_,x,y) ->
(*App (App (S, tr (Abs x)), tr (Abs y))*)
let f1 = free x
and f2 = free y in
if not f1 then
app (app B (tr x |> shift)) (tr (abstract y))
else if not f2 then
app (app C (tr (abstract x))) (tr y |> shift)
else
app (app S (tr (abstract x))) (tr (abstract y))
| _ ->
assert false
)
| t -> t

module Parser = struct
include ParserCombinators(struct type store = string list end)

let update f = fun s -> LazyList.singleton ((), { s with store = f s.store })

let lookup v =
let rec find i = function
| [] -> failwith "not found"
| v'::t ->
if v = v' then
i
else
find (i+1) t
in
fun s -> LazyList.singleton (find 0 s.store, s)

let term =
let rec pvar = lazy (ident_ >>= fun v -> var <$> lookup v)
and pabstract = lazy (
char_ '\\' >> many1 ident_ >>= fun vs ->
let l = List.length vs in
char_ '.' >>
update (fun ctx -> List.fold_left (fun ctx v -> v::ctx) ctx vs) >>
(nest l <$> Lazy.force term) <<
update (List.drop l)
)
and term0 = lazy ((char_ '(' >> (fun s -> Lazy.force term s) << char_ ')' <|> Lazy.force pabstract <|> Lazy.force pvar))
and term = lazy (List.fold_left1 app <$> many1 (Lazy.force term0))
in
Lazy.force term
end

let () =
let n = read_int () in
for i = 1 to n do
let s = read_line () in
match Parser.parse Parser.term [] s with
| None -> ()
| Some t -> tr t |> print; print_endline ""
done

Infer

https://www.hackerrank.com/challenges/infer

http://okmij.org/ftp/ML/generalization.html Didier Rémy提出的加速generalization的算法。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
module Str = struct
let implode l =
let s = Bytes.make (List.length l) ' ' in
List.iteri (fun i c -> Bytes.set s i c) l;
s
end

module LazyList = struct
type 'a node = Nil | Cons of 'a * 'a t
and 'a t = 'a node Lazy.t
let empty = lazy Nil
let singleton x = lazy (Cons (x, empty))
let force = Lazy.force
let rec map f l = lazy (
match force l with
| Nil -> Nil
| Cons (h, t) -> Cons (f h, map f t)
)
let rec append l1 l2 = lazy (
match force l1 with
| Nil -> force l2
| Cons (h, t) -> Cons (h, append t l2)
)
let rec concat ll = lazy (
match force ll with
| Nil -> Nil
| Cons (h, t) -> append h (concat t) |> force
)
let is_empty l = force l = Nil
end

module ParserCombinators = struct
type input = { s: bytes; pos: int }
type 'a t = input -> ('a * input) LazyList.t
let unit a s = LazyList.singleton (a, s)
let zero = unit []
let (>>=) (type a) (type b) (x : a t) (f : a -> b t) s =
LazyList.map (fun (a,s) -> f a s) (x s) |> LazyList.concat
let (>>) x y = x >>= fun _ -> y
let (<<) x y = x >>= fun a -> y >> unit a
let (<|>) x y s = let r = x s in if LazyList.is_empty r then y s else r
let (<$>) f x = x >>= fun a -> unit (f a)
let rec many x = many1 x <|> zero
and many1 x = x >>= fun b -> many x >>= fun bs -> unit (b::bs)
let sep_by x sep =
let go = x >>= fun b ->
many (sep >> x) >>= fun bs ->
unit (b::bs)
in
go <|> zero
let pred f s =
if s.pos = Bytes.length s.s then
LazyList.empty
else
let c = s.s.[s.pos] in
if f c then unit c { s with pos = s.pos + 1 } else LazyList.empty
let ident = Str.implode <$> many1 (pred (fun c ->
'a'<=c&&c<='z' || 'A'<=c&&c<='Z' || '0'<=c&&c<='9' || c = '_'))
let space = pred (fun c -> c = ' ' || c = '\t' || c = '\r' || c = '\n')
let token x = x >>= fun a -> many space >> unit a
let char c = pred ((=) c)
let str cs =
let rec go i =
if i = Bytes.length cs then
zero
else
char cs.[i] >> go (i+1)
in
go 0
let ident_ = token ident
let char_ c = token (char c)
let str_ cs = token (str cs)
end

type expr =
| Var of string
| Fun of string list * expr
| App of expr * expr list
| Let of string * expr * expr
type level = int
type typ =
| TConst of string
| TVar of tv ref
| TArrow of typ list * typ * levels
| TApp of typ * typ list * levels
and tv = Unbound of int * level | Link of typ
and levels = { mutable level_old : level; mutable level_new : level }
let gray_level = -1
let generic_level = 19921213

let rec djs_find = function
| TVar ({contents = Link t} as tv) ->
let t = djs_find t in
tv := Link t;
t
| t -> t

let get_level t =
match djs_find t with
| TConst _ -> 0
| TVar ({contents = Unbound (_, l)}) -> l
| TApp (_, _, ls)
| TArrow (_, _, ls) -> ls.level_new
| _ -> assert false

module Parser = struct
include ParserCombinators
let force = Lazy.force
let generic_ctr = ref 0
let tapp f args =
let l = List.fold_left (fun acc a ->
max acc (get_level a)) (get_level f) args in
TApp (f, args, { level_old = l; level_new = l })
let tarrow args r =
let l = List.fold_left (fun acc a ->
max acc (get_level a)) (get_level r) args in
TArrow (args, r, { level_old = l; level_new = l })
let typ () =
let univ = Hashtbl.create 0 in
let rec parse_ident =
ident_ >>= fun n ->
unit @@
try TVar (ref @@ Link (Hashtbl.find univ n))
with Not_found -> TConst n
and parse_tys s = sep_by parse_ty (char_ ',') s
and parse_ty s = (
let t1 =
let rec bracket f =
(char_ '[' >> parse_tys << char_ ']' >>= fun args ->
bracket (tapp f args)) <|> unit f
in
parse_ident >>= bracket >>= fun f ->
(str_ "->" >> (fun s -> parse_ty s) >>= fun r ->
unit @@ tarrow [f] r) <|> unit f
in
let t2 =
char_ '(' >> parse_tys << char_ ')' >>= fun args ->
(str_ "->" >> parse_ty >>= fun r ->
unit @@ tarrow args r) <|> unit (List.hd args)
in
t1 <|> t2
) s
and parse_top s = (
(str_ "forall[" >> many ident_ << char_ ']' >>= fun vs ->
List.iteri (fun i v ->
decr generic_ctr;
Hashtbl.replace univ v (TVar (Unbound (!generic_ctr, generic_level) |> ref))) vs;
parse_ty) <|> parse_ty
) s
in
parse_top
let expr =
let rec parse_let s = (
str_ "let" >> ident_ >>= fun n ->
char_ '=' >> parse_expr >>= fun e ->
str_ "in" >>
parse_expr >>= fun b ->
unit @@ Let (n, e, b)
) s
and parse_fun s = (
str_ "fun" >> many ident_ >>= fun args ->
str_ "->" >> parse_expr >>= fun b ->
unit @@ Fun (args, b)
) s
and parse_simple_expr s = (
let first = (char_ '(' >> parse_expr << char_ ')') <|>
(ident_ >>= fun n -> unit @@ Var n)
in
let rec go a =
(char_ '(' >> sep_by parse_expr (char_ ',') << char_ ')' >>= fun b ->
go @@ App (a, b)) <|> unit a
in
first >>= go
) s
and parse_expr s = (
parse_let <|>
parse_fun <|>
parse_simple_expr
) s
in
parse_expr
let eof s =
if s.pos = Bytes.length s.s then
LazyList.singleton ((), s)
else
LazyList.empty
let parse x s =
match force ((many space >> x << eof) { s; pos = 0 }) with
| LazyList.Nil -> None
| LazyList.Cons ((x, _), _) -> Some x
end

exception Cycle
exception Fail
exception Length
let gensym_ctr = ref 0
let gensym () =
let n = !gensym_ctr in
incr gensym_ctr;
n
let reset_gensym () = gensym_ctr := 0
let cur_level = ref 0
let reset_level () = cur_level := 0
let enter_level () = incr cur_level
let leave_level () = decr cur_level
let new_var () = TVar (ref (Unbound (gensym (), !cur_level)))
let new_app f args = TApp (f, args, { level_new = !cur_level; level_old = !cur_level })
let new_arrow args r = TArrow (args, r, { level_new = !cur_level; level_old = !cur_level })

let adj_q = ref []
let reset_adj_q () = adj_q := []
let force_adj_q () =
let rec go l acc t =
match djs_find t with
| TVar ({contents = Unbound (n, l')} as tv) ->
if l < l' then
tv := Unbound (n, l);
acc
| TApp (_, _, ls)
| TArrow (_, _, ls) as t ->
if ls.level_new = gray_level then
raise Cycle;
if l < ls.level_new then
ls.level_new <- l;
one acc t
| _ -> acc
and one acc = function
| TApp (r, args, ls)
| TArrow (args, r, ls) as t ->
if ls.level_old <= !cur_level then
t::acc
else if ls.level_old = ls.level_new then
acc
else (
let lvl = ls.level_new in
ls.level_new <- gray_level;
let acc = List.fold_left (go lvl) acc args in
let acc = go lvl acc r in
ls.level_new <- lvl;
ls.level_old <- lvl;
acc
)
| _ -> assert false
in
adj_q := List.fold_left one [] !adj_q

let rec update_level l = function
| TConst _ ->
()
| TVar ({contents = Unbound (n, l')} as tv) ->
if l < l' then
tv := Unbound (n, l)
| TApp (_, _, ls)
| TArrow (_, _, ls) as t ->
if ls.level_new = gray_level then
raise Cycle;
if l < ls.level_new then (
if ls.level_new = ls.level_old then
adj_q := t :: !adj_q;
ls.level_new <- l
)
| _ -> assert false

let rec unify t1 t2 =
let t1 = djs_find t1 in
let t2 = djs_find t2 in
if t1 != t2 then
match t1, t2 with
| TConst t1, TConst t2 when t1 = t2 ->
()
| TVar ({contents = Unbound (_, l)} as tv), t'
| t', TVar ({contents = Unbound (_, l)} as tv) ->
update_level l t';
tv := Link t'
| TApp (r1, args1, l1), TApp (r2, args2, l2)
| TArrow (args1, r1, l1), TArrow (args2, r2, l2) ->
if l1.level_new = gray_level || l2.level_new = gray_level then
raise Cycle;
if List.length args1 <> List.length args2 then
raise Length;
let lvl = min l1.level_new l2.level_new in
l1.level_new <- gray_level;
l2.level_new <- gray_level;
List.iter2 (unify_level lvl) args1 args2;
unify_level lvl r1 r2;
l1.level_new <- lvl;
l2.level_new <- lvl
| _ -> raise Fail

and unify_level l t1 t2 =
let t1 = djs_find t1 in
update_level l t1;
unify t1 t2

let gen t =
let rec go t =
match djs_find t with
| TConst _ ->
()
| TVar ({contents = Unbound (n, l)} as tv) ->
if l > !cur_level then
tv := Unbound (n, generic_level)
| TApp (r, args, ls)
| TArrow (args, r, ls) ->
if ls.level_new > !cur_level then (
List.iter go args;
go r;
let lvl = List.fold_left (fun acc a -> max acc (get_level a)) (get_level r) args in
ls.level_new <- lvl;
ls.level_old <- lvl
)
| _ -> assert false
in
force_adj_q ();
go t

let inst t =
let subst = Hashtbl.create 0 in
let rec go = function
| TVar {contents = Unbound (n, l)} when l = generic_level ->
(try
Hashtbl.find subst n
with Not_found ->
let tv = new_var () in
Hashtbl.replace subst n tv;
tv)
| TVar {contents = Link t} ->
go t
| TApp (f, args, ls) when ls.level_new = generic_level ->
new_app (go f) (List.map go args)
| TArrow (args, r, ls) when ls.level_new = generic_level ->
new_arrow (List.map go args) (go r)
| t -> t
in
go t

let rec typeof env e =
let rec go = function
| Var x -> Hashtbl.find env x |> inst
| Fun (args, e) ->
let ty_args = List.map (fun x -> new_var ()) args in
List.iter2 (Hashtbl.add env) args ty_args;
let ty_e = go e in
let r = new_arrow ty_args ty_e in
List.iter (Hashtbl.remove env) args;
r
| App (e, args) ->
let ty_fun = go e in
let ty_args = List.map go args in
let ty_res = new_var () in
unify ty_fun (new_arrow ty_args ty_res);
ty_res
| Let (x, e1, e2) ->
enter_level ();
let ty_e1 = go e1 in
leave_level ();
gen ty_e1;
Hashtbl.add env x ty_e1;
let r = go e2 in
Hashtbl.remove env x;
r
in
go e

let rec check_cycle = function
| TVar {contents = Link t} ->
check_cycle t
| TApp (r, args, ls)
| TArrow (args, r, ls) ->
if ls.level_new = gray_level then
raise Cycle;
let lvl = ls.level_new in
ls.level_new <- gray_level;
List.iter check_cycle args;
check_cycle r;
ls.level_new <- lvl
| _ -> ()

let rec top_typeof env e =
reset_gensym ();
reset_level ();
reset_adj_q ();
let t = typeof env e in
check_cycle t;
t

let rec show t =
let open Printf in
let id2name = Hashtbl.create 0 in
let rec go t =
match djs_find t with
| TConst n -> n
| TVar ({contents = Unbound (n, _)}) ->
(try
Hashtbl.find id2name n
with _ ->
let i = Hashtbl.length id2name in
let name = Char.chr (Char.code 'a' + i) |> String.make 1 in
Hashtbl.replace id2name n name;
name)
| TApp (f, args, _) ->
let u = go f in
let v = String.concat ", " (List.map go args) in
sprintf "%s[%s]" u v
| TArrow (args, r, _) ->
let f = function
| TArrow _ -> false
| _ -> true
in
let u = String.concat ", " (List.map go args) in
let v = go r in
if List.length args = 1 && f @@ djs_find (List.hd args) then
sprintf "%s -> %s" u v
else
sprintf "(%s) -> %s" u v
| _ -> assert false
in
let s = go t in
let l = Hashtbl.length id2name in
if l > 0 then (
let vs = Hashtbl.fold (fun _ v l -> v::l) id2name [] |> List.sort compare in
sprintf "forall[%s] %s" (String.concat " " vs) s
) else
s

let extract = function
| Some x -> x
| None -> assert false

let core =
[ "head", "forall[a] list[a] -> a"
; "tail", "forall[a] list[a] -> list[a]"
; "nil", "forall[a] list[a]"
; "cons", "forall[a] (a, list[a]) -> list[a]"
; "cons_curry", "forall[a] a -> list[a] -> list[a]"
; "map", "forall[a b] (a -> b, list[a]) -> list[b]"
; "map_curry", "forall[a b] (a -> b) -> list[a] -> list[b]"
; "one", "int"
; "zero", "int"
; "succ", "int -> int"
; "plus", "(int, int) -> int"
; "eq", "forall[a] (a, a) -> bool"
; "eq_curry", "forall[a] a -> a -> bool"
; "not", "bool -> bool"
; "true", "bool"
; "false", "bool"
; "pair", "forall[a b] (a, b) -> pair[a, b]"
; "pair_curry", "forall[a b] a -> b -> pair[a, b]"
; "first", "forall[a b] pair[a, b] -> a"
; "second", "forall[a b] pair[a, b] -> b"
; "id", "forall[a] a -> a"
; "const", "forall[a b] a -> b -> a"
; "apply", "forall[a b] (a -> b, a) -> b"
; "apply_curry", "forall[a b] (a -> b) -> a -> b"
; "choose", "forall[a] (a, a) -> a"
; "choose_curry", "forall[a] a -> a -> a"
]

let core_env =
let env = Hashtbl.create 0 in
List.iter (fun (var, typ) ->
let t = Parser.parse (Parser.typ ()) typ |> extract in
Hashtbl.replace env var t
) core;
env

let type_check line =
let env = Hashtbl.copy core_env in
Parser.parse Parser.expr line |> extract |> top_typeof env

let () =
read_line () |> type_check |> show |> print_endline

Android微信数据导出

在Nexus 5(Android 4.4)+WeChat 5.4,和Nexus 5(Android 5.0)+Wechat 6.0上测试可用。

获取加密的sqlite3数据库EnMicroMsg.db

如果已经root过,可以下载/data/data/com.tencent.mm/MicroMsg/*/EnMicroMsg.db

若没有root,则/data/data/com.tencent.mm下多数目录都不可读,可以使用下面的方法:

  • 开启“开发人员选项”,选上“USB侦错”
  • 电脑上执行adb backup -noapk com.tencent.mm
  • 在手机上弹出对话框提示是否允许备份
  • 不要设置密码,点备份,电脑会收到backup.ab
  • 解压backup.abdd if=backup.ab bs=24 skip=1 | openssl zlib -d > backup.tar
  • 解压backup.tar得到数据库apps/com.tencent.mm/r/MicroMsg/*/EnMicroMsg.db

Read More

DEFCON 22 CTF参赛记

8月5日

感谢赞助商安全宝给我们的支持,不然我们即使有决赛入场券也难以成行。去年参加DEFCON 21 CTF时,由于航班延误到第二天,比赛前一天才到达Las Vegas,把大家都弄得疲惫不堪。吸取去年的教训,今年我们决定提前两天到。我和zTrix、cbmixx、DeadCat等同行,从北京出发,其他伙伴则从上海出发。巧的是和TombKeeper一个航班……

Read More

ISC'14 Student Cluster Competition

本学期期末参加了ISC'14 Student Cluster Competition,6月20日到6月27日住在Leipzig Messe的Sachsenpark Hotel。

6月20日

从北京出发,在Frankfurt转机抵达Leipzig。Frughafen Leipzig竟然没免费WiFi……手机电也不足了,也不知道无线网怎么弄,给先到达的伙伴们打了三个电话,费了好大功夫坐S-bahn乘到Leipzig Messe。看到ISC'14广告牌很激动呢。

会场旁的Leipzig吉祥物,四只小狮子,好萌~ 吉祥物

Read More

LeetCode solutions

You have solved 489/1771 problems. 主要追求两个目标:代码简短,时间空间复杂度低。

注记

4-sum

使用了multimap,时间复杂度,得到所有答案后不需要去重操作。

合法的四元组有三类:

  • a<=b<c<=d,枚举cd,判断是否存在和为target-c-d的二元组
  • a<=b=c<=d,枚举bd,判断是否存在target-b-b-d
  • a=b=c<=d,枚举a,判断是否存在target-a-a-a

分别统计,小心实现可以保证不会产生相同的候选解,从而无需去重。

Alien Dictionary

对于每一对单词,可以确定去除最长公共前缀后的下一对字母的大小关系。两个单词的最长公共前缀等于夹在其中的(所有相邻单词对的最长公共前缀)的最小值。根据相邻单词对的信息即可推得所有任意单词对的信息。因此只需根据相邻单词对求出拓扑关系。

Basic Calculator

这是operator-precedence grammar,可以用operator-precedence parser计算。这类算法的一个特例是shunting-yard algorithm,适用于本题。 为了方便,我假设字串开头和末尾都有隐含的'\0'字符。使用的文法如下:

1
2
3
4
5
S := %x00 E %x00
E := E "+" E
E := E "-" E
E := ( E )
E := 1*DIGIT

参考http://www.scribd.com/doc/51358638/16/Operator-Precedence-Relations

在比较两个操作符时,区分左手边和右手边,左手边用于先处理的操作符,右手边为新来的操作符。使用左手边操作符的in-stack precedence(isp)和右手边操作符的incoming precedence(icp)进行比较。立即数可以看作icp很大,因此shift后可以立刻reduce。

Best Time to Buy and Sell Stock IV

线性解法。见2015-03-27-leetcode-best-time-to-buy-and-sell-stock-iv

Closest Binary Search Tree Value II

题意:求BST中与目标值最接近的k个节点。 BST中关键字小于等于目标值的所有节点可以用若干(不带右孩子的子树)表示。这些(不带右孩子的子树)在一条链上,可以用栈维护,得到用于计算前驱的的迭代器。求出目标值的k个前驱的时间复杂度为。 类似地,大于目标值的所有节点也可以组织成一个迭代器。 两个迭代器做合并操作,获得前k个最接近的值。

Contains Duplicate III

为单位把元素分桶,若一个桶内包含两个元素,则它们的差一定小于等于;差小于等于的数对还可能出现在相邻两个桶之间。对于的各个元素,计算当前元素应放置的桶的编号,检查三个桶,判断之前个元素里是否有差值小于等于的元素。

Course Schedule

拓扑排序。入度减为0的顶点即成为候选,可以把入度向量组织成单链表,从而无需使用额外的队列或栈存储候选顶点,减小空间占用。

Dungeon Game

动态规划,对于每个格子记录从它出发顺利到达终点需要的最小血量。从递推至

注意对于每个格子其实有进和出两个状态:进入该格子时(未考虑当前格子影响);和离开该格子后(已考虑当前格子影响)。这两种方法都行,考虑到程序的结构可能有三部分:初始化边界条件、状态转移、根据状态表示答案,需要仔细斟酌以追求代码简短。这里两种方式并无明显代码长度差异。

Expression Add Operators

2015-10-16-leetcode-expression-add-operators

Find Minimum in Rotated Sorted Array

方法是二分,如果要写短可以采用下面的思路: 子数组中如果有相邻两个元素a[i]>a[i+1],则a[i+1]是整个数组的最小值。 若子数组a[i..j]满足a[i]>a[j],则存在i<=k<j使得a[k]>a[k+1]。 对于子数组a[l..h]判断a[l]>a[m]a[m]>a[h]是否有一个成立,成立则可以去除一半候选元素,不然a[h]>a[l]为一个逆序对。

Find Minimum in Rotated Sorted Array II

留意几个特殊情形:[1,0,1,1,1][1,1,1,0,1]

对于子数组a[l..h],令m=floor(l+h)/2(注意m可能等于l)。判断a[l]>a[m]a[m]>a[h]是否有一个成立,成立则可以去除一半候选元素。 若两个条件均不满足则a[l]<=a[m]<=a[h],若a[h]>a[l]则说明a[l]最小,否则a[l]=a[m]=a[h],可以把范围缩小为a[l+1..h-1]

另外一种方法是只判断a[m]与a[h]`的大小关系。

Find Peak Element

二分查找,把区间缩小为仍包含候选值的子区间。对于相邻两个元素,若及左边部分存在peak,否则及右边部分存在peak。不关心是否满足peak条件,将区间折半。

1
2
3
4
5
6
7
int l = 0, h = a.size();
while (l < h-1) {
int m = l+h >> 1;
if (a[m-1] > a[m]) h = m;
else l = m;
}
return l;

或者检查中间元素是否满足要求,可以提前退出循环。

1
2
3
4
5
6
7
8
int l = 0, h = a.size();
while (l < h-1) {
int m = l+h >> 1;
if (a[m-1] > a[m]) h = m;
else if (m+1 == h || a[m] > a[m+1]) l = h = m;
else l = m+1;
}
return l;

First Missing Possitive

空间复杂度

Fraction to Recurring Decimal

注意INT_MIN/(-1)会溢出。

Graph Valid Tree

个节点的树的判定方式:

  • 条边且没有simple circle。可以用union-find algorithm判断。
  • 联通且无simple circle。可以用graph traversal。

Guess Number Higher or Lower II

动态规划优化,。见张昆玮的分析:http://artofproblemsolving.com/community/c296841h1273742s3_leetcode_guess_number_higher_or_lower_ii

Invert Binary Tree

选择一种binary tree traversal算法,节点访问改成交换左右孩子即可。 如果要O(1)空间的话,得借鉴Morris pre/in-order traversal的思路,该算法的核心是通过左子树最右节点的右孩子是否指向当前节点来判断当前节点被访问到的次数,从而决定当前应该进行的操作(探索左子树或访问当前节点)。但交换子树操作会弄乱左子树最右节点的位置,因此pre-order和in-order都行不通,但post-order可行。Morris post-order traversal(这个叫法也许不恰当)可以参考https://www.quora.com/What-is-a-good-way-to-implement-stackless-recursion-less-post-order-traversal-for-a-non-threaded-binary-tree-using-Morris-method的描述,pre/in-order的访问是针对一个节点进行的,但post-order则需要对当前节点左子树的右链进行,并且需要翻转两次以达到按post-order输出的效果。但这里只需要保证每个节点都被访问一次,不需要严格的post-order顺序,因此无需翻转操作。

Jump Game

空间复杂度

Jump Game II

使用output-restricted queue优化的动态规划,注意到动态规划值的单增性可以用类似BFS的方式,空间复杂度

Lexicographical Numbers

在trie中找1~n,存在迭代解法。

Linked List Cycle II

单链表找圈。Brent's cycle detection algorithm或Floyd's cycle detection algorithm。

如果只需要判断是否有圈,而不用指出圈的起点,可以使用pointer reversal。访问链表的过程中翻转链表,倘若访问到NULL,则说明无圈;若回到了起点,则说明有圈。如果有圈的话,算法执行完毕后,圈的方向会被反转,可以再执行一次翻转过程还原。下面是这个方法的实现:

1
2
3
4
5
6
7
8
9
10
11
12
// return true if a cycle is detected
bool pointerReversal(ListNode *head) {
if (! head) return false;
ListNode *x = head->next, *y, *z = head;
while (x && x != head) {
y = x->next;
x->next = z;
z = x;
x = y;
}
return x == head;
}

Longest Palindromic Substring

线性时间求出以每个位置为中心的最长回文子串的Manacher's algorithm。http://www.csie.ntnu.edu.tw/~u91029/Palindrome.html提供的描述感觉最清晰。但实现我更喜欢我从某本stringology书上看到的。

Majority Element

Boyer-Moore majority vote algorithm http://www.cs.utexas.edu/~moore/best-ideas/mjrty/,思路是每次找到两个不同的元素并丢弃,这样做不会丢失解。容器里只剩下一种元素时,它就是majority。

Majority Element II

Boyer-Moore majority vote algorithm的扩展,找出所有出现次数大于的元素。方法是每次找出个互不相同的元素丢掉,最后剩下的元素是候选解。时间复杂度

Maximum Gap

平均数原理,求出极差后,根据桶大小分成若干个桶,答案必为不同桶的两个元素之差。

Maximum Subarray

Kadane's algorithm

Meeting Rooms II

题意中两条线段冲突当且仅当它们的公共部分长度大于0。 这是interval graph,所求的是chromatic number,interval graph包含与perfect graph,因此chromatic number等于maximum clique顶点数,即最大线段相交数,可以把所有端点排序计算。 或者按起始端点排序后用贪心算法:维护若干线段集合,按起始端点总从小到大考虑每个线段,任选一个不冲突的集合加入,若无不冲突的集合则自成一个新集合。最后,集合数即为答案。实现时,每个集合用最大右端点值表示,所有集合组织为一个小根binary heap,若当前考虑线段的起始点小于根则压入一个新元素,否则修改根的值。

Merge k Sorted Lists

Tournament sort,可以用priority_queue实现。

Min Stack

使用两个栈,原栈S存放各个元素。每当新元素小于等于当前最小值时,就把新元素复制一份压入另一个栈S'。弹出时,若元素在S'中出现,则也从S'中弹出。

另一种方法是记录新元素与当前最小值的差值,每个元素需要多记录1个bit。可惜C++会Memory Limit Exceeded,感觉不合理。

Minimum Window Substring

尺取法

Missing Number

从左到右考虑每个元素,若不等于它的位置则把它交换到正确的位置并重复此过程。

N Queen

bitmask存储列,正反斜线控制的格子。

Number of 1 Bits

求popcount。__builtin_popcount()或者网上查找各种bit twiddling hacks。

One Edit Distance

编辑距离为1有三种可能:S比T多一个字符、T比S多一个字符、S与T长度相同且有一个位置不同。除去最长公共前缀和最长公共后缀,三种可能的检查方式可以统一为判断较长的串长度是否为1。

Palindrome Partitioning

f[i][j] = calc(f[ii][jj] : i <= ii <= jj <= j)形式的动态规划可以采用如下计算方式。

1
2
3
4
for (int i = n; --i >= 0; )
for (int j = i; j < n; j++) {
// calc [i,j]
}

Palindrome Partitioning II

求原串的最少回文串划分。O(n^2)时间,可以优化到O(n)空间。

我没能找到比O(n^2)快的算法。相关的问题有检测一个串是否分割成k个回文串。k小于等于4时均有线性算法,参见Text Algorithms一书Theorem 8.17。k大于4时不确定。

Perfect Rectangle

使用unordered_map解法:判断除了四个极点,每个小矩形的角是否被两个或四个矩形共享。

或者判断所有小矩形面积和等于四个极点围成的矩形的面积,并且小矩形没有重叠(用sweep line判断)。

Perfect Squares

https://leetcode.com/discuss/57477/sqrt-applying-fermats-theorm-brahmagupta-fibonacci-identity

由Lagrange's four-square theorem知答案为1~4,由Legendre's three-square theorem检查答案是否为4。若小于4,则再尺取法检查是否是perfect square或能表示为两个perfect squares之和,若不是则答案为3。

另有期望的算法,参见M. O. Rabin, J. O. Shallit, Randomized Algorithms in Number Theory, Communications on Pure and Applied Mathematics 39 (1986), no. S1, pp. S239–S256. doi:10.1002/cpa.3160390713

Reconstruct Itinerary

题目即lexicographically smallest Eulerian path。Eulerian path最简单的算法是Hierholzer's algorithm,有向图中仅有一个顶点出度=入度+1,记为源;一个顶点入度=出度+1,记为汇。任求一条源到汇的路径,之后把各个圈合并到路径上即可。本题要求字典序最小,对Hierholzer's algorithm稍加变形即可。

从源开始,贪心地选择序号最小的下一个顶点,删除这条边,重复此过程,即得到一条源到汇的路径。需要把圈添加到该路径上。若一个圈只包含路径上的一个顶点,那么在该顶点处添加圈即可。若一个圈包含路径上的多个顶点,那么应该把它放在离汇最近的顶点上,这样能保证字典序最小。

Recover Binary Search Tree

使用Morris in-order traversal找到邻接失序对。

如果交换的元素相邻,则有一个邻接失序对(如0 1 2 3 4 ->0 1 3 2 4),否则有两个邻接失序对(如0 1 2 3 4 5 -> 0 4 2 3 1 5)。

Remove Nth Node From End of List

http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions

使用pointers-to-pointers很多时候能简化实现。

Regular Expression Matching

P为模式串,T为文本, f[i][j]表示P的前i个字符能否匹配T的前j个字符。 根据f[i-1][*]计算f[i][*]。 这个方法也可以看作构建了精简表示的Thompson's automaton,时间复杂度

Remove Element

原地修改数组,我喜欢把这种操作称作deflate。

Remove Invalid Parentheses

最少移除个数很容易计算,把可以配对的左右括号全部抵消,剩余括号数即是(形如:)))...((()。难点在于输出所有不同答案,多数解法使用DFS枚举要删除哪些括号,枚举量大于答案个数。 有一个枚举量固定为答案个数的方法,找到残余串)))...(((中右括号与左括号的分割点。DFS分割点左半部分,保证到达残余串第个右括号时,至少有个右括号(原串的)被删除。分割点右半部分也如法炮制,两边合并即为答案。

Repeated DNA Sequences

可以用类似Rabin-Karp的rolling hash方法,求出所有长为10的子串的hash值,判断是否有重复。只有四个字符,长度为10,故可以使用polynomial hash code。 另外也可以用suffix tree/suffix array等方法,找longest common prefix大于等于10的两个后缀。注意不能重复输出字串。

Reverse Bits

Hacker's Delight (2nd) 7.1 Reversing Bits and Bytes。

Rotate Array

经典的三次reverse,或者拆成gcd(k,n)个置换群循环右移一格。

Same Tree

类似于same fringe problem,可以试验generator、co-routine、lazy evaluation、continuation等。如果要O(1)的空间复杂度可以用Morris in-order traversal等方法。

Set Matrix Zeroes

空间复杂度。使用两个标志表示第0行或第0列是否需要清零,之后用第0行表示各列是否需要清零,第0列表示各行是否需要清零。

Search For a Range

设序列用区间表示为[begin,end)。使用C++ STL风格的lower_bound、upper_bound。有几点好处:

  • 循环内只有一次比较
  • 循环退出后两个指针相等,且落在[begin,end],都是迭代器的合法取值。某些binary search写法返回值可能为begin-1,某些容器不合法
  • [lower_bound(a[],x), upper_bound(a[],x)给出了元素x所在的子区间

Search Insert Position

C++ <algorithm>lower_bound

Serialize and Deserialize Binary Tree

把NULL视作叶子,则pre/in/post-order traversal可以用于编码。若使用Morris traversal则额外空间为。解码时使用类似Schorr-Waite graph marking algorithm的edge crawling技巧即可做到额外空间

Shortest Palindrome

找出原串的最长回文前缀,用Manacher's algorithm求解,把剩下部分复制一份、翻转后、接到左边,就得到了最短的回文串。求最长回文前缀的另一种方法是把原串以及翻转用特殊字符隔开,用Morris-Pratt algorithm求border,该值即为最长回文前缀长度。

Single Number III

所有数的xor等于两个出现一次的数的xor,不妨设为k,则k & -k为二进制表示上某个为1的数位。根据这个数位把所有元素划分成两份,每份只有一个出现一次的数。

Smallest Good Base

,由,由,因此。枚举唯一可能取值为,判断是否成立。

Sort Colors

Dutch national flag problem。如果不要求000111222,允许111000222111,那么有交换次数更少的Bentley-McIlroy算法http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-flag-problem-3/

Sqrt(x)

Hacker's Delight (2nd) 11.1.1。 牛顿迭代法。46340 = floor(sqrt(INT_MAX))

Scramble String

我用了的空间和的时间,应该有更好的算法。但查阅了一些文献还没有找到。

Sort List

我用了较麻烦的natural merge sort。Quicksort实现会简单很多。

Strobogrammatic Number III

定义一个函数,用于计算小于给定数的strobogrammatic number个数,则用减法即可得到题目所求。下面考虑如何计算这个函数。 小于给定数high的strobogrammatic number分为两类:

  • 位数不够的,可看作有若干前导0。容易求得。
  • 位数相同。可以枚举与high的公共前缀的长度,再计算下一个数位小于high中对应数位的strobogrammatic number个数。由于位数为的strobogrammatic number只有个数位是独立的,枚举的公共前缀长度得小于

Sudoku Solver

转化为exact cover problem,使用dancing links + Algorithm X求解。

Trapping Rain Water

两个指针夹逼,空间

Unique Binary Search Trees II

类似动态规划的思想,子树可以复用。

Wiggle Sort

从左到右考虑每一对相邻元素,如果不满足大小关系则交换,交换不会影响之前一对元素的大小关系。

Word Ladder

基本方法是BFS或bidirectional BFS,相邻关系的确定有两种思路:枚举所有其他顶点判断是否相邻、枚举顶点的变异判断是否为顶点。对于第一种思路,还可以利用一个技巧:把所有字串都分为左右两半,若两个字串hamming distance为1,则左半部分相同或右半部分相同。

Verify Preorder Sequence in Binary Search Tree

对于前序序列中的递减连续段,它们形成了BST的某个左孩子链。

Maximal Rectangle

秋叶拓哉(iwi)、岩田阳一(wata)和北川宜稔(kita_masa)所著,巫泽俊(watashi)、庄俊元(navi)和李津羽(itsuhane)翻译的《挑战程序设计竞赛》

逐行扫描棋盘,对于每一行记录三个值:

  • 表示第列上方连续为1的行数:h[j] = a[i][j] == 0 ? 0 : h[j]+1;
  • ,令;若则设为
  • ,令;若则设为

的计算方式是:

1
2
3
4
5
6
7
if a[i][j] == 0:
l[j] = j
elif h[j] == 1:
l[j] = j-(a[i][j]及左边连续的1的个数)+1
else
# 下式中右边的l[j]是第i-1行计算得到的l[j]
l[j] = min(l[j], j-(a[i][j]及左边连续的1的个数)+1)

的计算类似。对于每一列是一个候选解。

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
#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

class Solution {
public:
int maximalRectangle(vector<vector<char> > &a) {
if (a.empty()) return 0;
int m = a.size(), n = a[0].size(), ans = 0;
vector<int> h(n), l(n), r(n, n-1);
REP(i, m) {
int ll = -1;
REP(j, n) {
h[j] = a[i][j] == '1' ? h[j]+1 : 0;
if (a[i][j] == '0') ll = j;
l[j] = h[j] ? max(h[j] == 1 ? 0 : l[j], ll+1) : j;
}
int rr = n;
ROF(j, 0, n) {
if (a[i][j] == '0') rr = j;
r[j] = h[j] ? min(h[j] == 1 ? n-1 : r[j], rr-1) : j;
ans = max(ans, (r[j]-l[j]+1)*h[j]);
}
}
return ans;
}
};

潘宇超 2008

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
#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

class Solution {
public:
int maximalRectangle(vector<vector<char> > &a) {
if (a.empty()) return 0;
int m = a.size(), n = a[0].size(), ans = 0;
vector<int> h(n), l(n), r(n, n-1);
REP(i, m) {
REP(j, n) {
h[j] = a[i][j] == '1' ? h[j]+1 : 0;
l[j] = j;
while (l[j] && h[l[j]-1] >= h[j])
l[j] = l[l[j]-1];
}
ROF(j, 0, n) {
r[j] = j;
while (r[j]+1 < n && h[j] <= h[r[j]+1])
r[j] = r[r[j]+1];
ans = max(ans, (r[j]-l[j]+1)*h[j]);
}
}
return ans;
}
};

ACRush某TopCoder SRM

逐行扫描棋盘,对于每一行记录:第列上方连续为1的行数。

对于每一行,从大到小排序,并计算候选解:

1
2
3
4
x = [0,0,...,0]
foreach j, h[j]: # 从大到小遍历h[j]
x[j] = 1
ans = max(ans, (max(k : x[j..k]都为1) - min(k : x[k..j]都为1)) * h[j])

上面伪代码可以在时间内求出。方法是把中设置为1的元素看成若干集合,相邻元素在同一个集合中。每次把某个中元素设为1可以看成新建了一个集合,若左边或右边的集合存在则合并。

不相交集合可以用union-find算法,但针对这种特殊情形存在的算法:每个集合(即某个1的连续段)左端和右端互指,其他元素的指针任意。新建集合时若左边或右边的集合存在,则更新它们两端的指针。

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
#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP1(i, n) for (int i = 1; i <= (n); i++)

class Solution {
public:
int maximalRectangle(vector<vector<char> > &a) {
if (a.empty()) return 0;
int m = a.size(), n = a[0].size(), ans = 0;
vector<int> h(n), p(n), b(m+1), s(n);
REP(i, m) {
REP(j, n)
h[j] = a[i][j] == '1' ? h[j]+1 : 0;
fill(b.begin(), b.end(), 0);
REP(j, n)
b[h[j]]++;
REP1(j, m)
b[j] += b[j-1];
REP(j, n)
s[--b[h[j]]] = j;
fill(p.begin(), p.end(), -1);
ROF(j, 0, n) {
int x = s[j], l = x, r = x;
p[x] = x;
if (x && p[x-1] != -1) {
l = p[x-1];
p[l] = x;
p[x] = l;
}
if (x+1 < n && p[x+1] != -1) {
l = p[x];
r = p[x+1];
p[l] = r;
p[r] = l;
}
ans = max(ans, (r-l+1)*h[x]);
}
}
return ans;
}
};

栈维护histogram

逐行扫描棋盘,对于每一行记录:第列上方连续为1的行数。

对于每一行,维护一个以值为元素的栈,满足从栈底到栈顶值递增。从左到右枚举各列,在插入前维持栈性质,弹出元素后栈顶代表往左能“看到”的最远位置,插入

其他方法 

枚举两列,求出夹在两列间的最大1子矩形。

表示以原矩形最上角和两个端点的矩形内1的数目,枚举所有子矩形,用求出这个子矩形内1的数目,判断是否合法。

把0看成障碍点,求不包含障碍点的最大子矩形。 把障碍点按横座标排序。枚举障碍点作为候选子矩形的左端,向右扫描各个障碍点,维护纵座标和枚举点最近的上下个一个障碍点。枚举点、扫描线和上下障碍点确定了候选子矩形的边界。 若0的数目为,,最坏

代码索引

# Title Solution
1897 Maximize Palindrome Length From Subsequences maximize-palindrome-length-from-subsequences.cc
1896 Maximum Score from Performing Multiplication Operations maximum-score-from-performing-multiplication-operations.cc
1895 Minimum Number of Operations to Move All Balls to Each Box minimum-number-of-operations-to-move-all-balls-to-each-box.cc
1894 Merge Strings Alternately merge-strings-alternately.cc
1876 Map of Highest Peak map-of-highest-peak.cc
1875 Tree of Coprimes tree-of-coprimes.cc
1874 Form Array by Concatenating Subarrays of Another Array form-array-by-concatenating-subarrays-of-another-array.cc
916 Decoded String at Index decoded-string-at-index.cc
830 Largest Triangle Area largest-triangle-area.cc
673 Number of Longest Increasing Subsequence number-of-longest-increasing-subsequence.cc
635 Design Log Storage System design-log-storage-system.cc
634 Find the Derangement of An Array find-the-derangement-of-an-array.cc
633 Sum of Square Numbers sum-of-square-numbers.cc
631 Design Excel Sum Formula design-excel-sum-formula.cc
630 Course Schedule III course-schedule-iii.cc
629 K Inverse Pairs Array k-inverse-pairs-array.cc
628 Maximum Product of Three Numbers maximum-product-of-three-numbers.cc
617 Merge Two Binary Trees merge-two-binary-trees.cc
616 Add Bold Tag in String add-bold-tag-in-string.cc
611 Valid Triangle Number valid-triangle-number.cc
604 Design Compressed String Iterator design-compressed-string-iterator.cc
600 Non-negative Integers without Consecutive Ones non-negative-integers-without-consecutive-ones.cc
599 Minimum Index Sum of Two Lists minimum-index-sum-of-two-lists.cc
598 Range Addition II range-addition-ii.cc
594 Longest Harmonious Subsequence longest-harmonious-subsequence.cc
593 Valid Square valid-square.cc
592 Fraction Addition and Subtraction fraction-addition-and-subtraction.cc
588 Design In-Memory File System design-in-memory-file-system.cc
587 Erect the Fence erect-the-fence.cc
583 Delete Operation for Two Strings delete-operation-for-two-strings.cc
582 Kill Process kill-process.cc
581 Shortest Unsorted Continuous Subarray shortest-unsorted-continuous-subarray.cc
575 Distribute Candies distribute-candies.cc
565 Array Nesting array-nesting.cc
556 Next Greater Element III next-greater-element-iii.cc
553 Optimal Division optimal-division.cc
552 Student Attendance Record II student-attendance-record-ii.cc
533 Lonely Pixel II lonely-pixel-ii.cc
531 Lonely Pixel I lonely-pixel-i.cc
514 Freedom Trail freedom-trail.cc
508 Most Frequent Subtree Sum most-frequent-subtree-sum.cc
507 Perfect Number perfect-number.cc
504 Base 7 base-7.cc
502 IPO ipo.cc
501 Find Mode in Binary Search Tree find-mode-in-binary-search-tree.cc
500 Keyboard Row keyboard-row.cc
495 Teemo Attacking teemo-attacking.cc
494 Target Sum target-sum.cc
491 Increasing Subsequences increasing-subsequences.cc
490 The Maze the-maze.cc
485 Max Consecutive Ones max-consecutive-ones.cc
483 Smallest Good Base smallest-good-base.cc
482 License Key Formatting license-key-formatting.cc
481 Magical String magical-string.cc
480 Sliding Window Median sliding-window-median.cc
477 Total Hamming Distance total-hamming-distance.cc
476 Number Complement number-complement.cc
475 Heaters heaters.cc
474 Ones and Zeroes ones-and-zeroes.cc
473 Matchsticks to Square matchsticks-to-square.cc
472 Concatenated Words concatenated-words.cc
469 Convex Polygon convex-polygon.cc
468 Validate IP Address validate-ip-address.cc
467 Unique Substrings in Wraparound String unique-substrings-in-wraparound-string.cc
466 Count The Repetitions count-the-repetitions.cc
465 Optimal Account Balancing optimal-account-balancing.cc
464 Can I Win can-i-win.cc
463 Island Perimeter island-perimeter.cc
462 Minimum Moves to Equal Array Elements II minimum-moves-to-equal-array-elements-ii.cc
461 Hamming Distance hamming-distance.cc
459 Repeated Substring Pattern repeated-substring-pattern.cc
456 132 Pattern 132-pattern.cc
455 Assign Cookies assign-cookies.cc
454 4Sum II 4sum-ii.cc
453 Minimum Moves to Equal Array Elements minimum-moves-to-equal-array-elements.cc
452 Minimum Number of Arrows to Burst Balloons minimum-number-of-arrows-to-burst-balloons.cc
447 Number of Boomerangs number-of-boomerangs.cc
446 Arithmetic Slices II - Subsequence arithmetic-slices-ii-subsequence.cc
444 Sequence Reconstruction sequence-reconstruction.cc
441 Arranging Coins arranging-coins.cc
440 K-th Smallest in Lexicographical Order k-th-smallest-in-lexicographical-order.cc
439 Ternary Expression Parser ternary-expression-parser.cc
438 Find All Anagrams in a String find-all-anagrams-in-a-string.cc
437 Path Sum III path-sum-iii.cc
436 Find Right Interval find-right-interval.cc
435 Non-overlapping Intervals non-overlapping-intervals.cc
434 Number of Segments in a String number-of-segments-in-a-string.cc
432 All O`one Data Structure all-oone-data-structure.cc
424 Longest Repeating Character Replacement longest-repeating-character-replacement.cc
423 Reconstruct Original Digits from English reconstruct-original-digits-from-english.cc
422 Valid Word Square valid-word-square.cc
421 Maximum XOR of Two Numbers in an Array maximum-xor-of-two-numbers-in-an-array.cc
420 Strong Password Checker strong-password-checker.cc
419 Battleships in a Board battleships-in-a-board.cc
417 Pacific Atlantic Water Flow pacific-atlantic-water-flow.cc
416 Partition Equal Subset Sum partition-equal-subset-sum.cc
415 Add Strings add-strings.cc
414 Third Maximum Number third-maximum-number.cc
413 Arithmetic Slices arithmetic-slices.cc
412 Fizz Buzz fizz-buzz.cc
410 Split Array Largest Sum split-array-largest-sum.cc
409 Longest Palindrome longest-palindrome.cc
408 Valid Word Abbreviation valid-word-abbreviation.cc
407 Trapping Rain Water II trapping-rain-water-ii.cc
406 Queue Reconstruction by Height queue-reconstruction-by-height.cc
405 Convert a Number to Hexadecimal convert-a-number-to-hexadecimal.cc
404 Sum of Left Leaves sum-of-left-leaves.cc
403 Frog Jump frog-jump.cc
402 Remove K Digits remove-k-digits.cc
401 Binary Watch binary-watch.cc
400 Nth Digit nth-digit.cc
399 Evaluate Division evaluate-division.cc
398 Random Pick Index random-pick-index.cc
397 Integer Replacement integer-replacement.cc
396 Rotate Function rotate-function.cc
395 Longest Substring with At Least K Repeating Characters longest-substring-with-at-least-k-repeating-characters.cc
394 Decode String decode-string.cc
393 UTF-8 Validation utf-8-validation.cc
392 Is Subsequence is-subsequence.cc
391 Perfect Rectangle perfect-rectangle.cc
390 Elimination Game elimination-game.cc
389 Find the Difference find-the-difference.cc
388 Longest Absolute File Path longest-absolute-file-path.cc
387 First Unique Character in a String first-unique-character-in-a-string.cc
386 Lexicographical Numbers lexicographical-numbers.cc
385 Mini Parser mini-parser.cc
384 Shuffle an Array shuffle-an-array.cc
383 Ransom Note ransom-note.cc
382 Linked List Random Node linked-list-random-node.cc
381 Insert Delete GetRandom O(1) - Duplicates allowed insert-delete-getrandom-o1-duplicates-allowed.cc
380 Insert Delete GetRandom O(1) insert-delete-getrandom-o1.cc
379 Design Phone Directory design-phone-directory.cc
378 Kth Smallest Element in a Sorted Matrix kth-smallest-element-in-a-sorted-matrix.cc
377 Combination Sum IV combination-sum-iv.cc
376 Wiggle Subsequence wiggle-subsequence.cc
375 Guess Number Higher or Lower II guess-number-higher-or-lower-ii.cc
374 Guess Number Higher or Lower guess-number-higher-or-lower.cc
373 Find K Pairs with Smallest Sums find-k-pairs-with-smallest-sums.cc
372 Super Pow super-pow.cc
371 Sum of Two Integers sum-of-two-integers.cc
370 Range Addition range-addition.cc
369 Plus One Linked List plus-one-linked-list.cc
368 Largest Divisible Subset largest-divisible-subset.cc
367 Valid Perfect Square valid-perfect-square.cc
366 Find Leaves of Binary Tree find-leaves-of-binary-tree.cc
365 Water and Jug Problem water-and-jug-problem.cc
364 Nested List Weight Sum II nested-list-weight-sum-ii.cc
362 Design Hit Counter design-hit-counter.cc
361 Bomb Enemy bomb-enemy.cc
360 Sort Transformed Array sort-transformed-array.cc
359 Logger Rate Limiter logger-rate-limiter.cc
358 Rearrange String k Distance Apart rearrange-string-k-distance-apart.cc
357 Count Numbers with Unique Digits count-numbers-with-unique-digits.cc
356 Line Reflection line-reflection.cc
355 Design Twitter design-twitter.cc
354 Russian Doll Envelopes russian-doll-envelopes.cc
353 Design Snake Game design-snake-game.cc
352 Data Stream as Disjoint Intervals data-stream-as-disjoint-intervals.cc
351 Android Unlock Patterns android-unlock-patterns.cc
350 Intersection of Two Arrays II intersection-of-two-arrays-ii.cc
349 Intersection of Two Arrays intersection-of-two-arrays.cc
348 Design Tic-Tac-Toe design-tic-tac-toe.cc
347 Top K Frequent Elements top-k-frequent-elements.cc
346 Moving Average from Data Stream moving-average-from-data-stream.cc
345 Reverse Vowels of a String reverse-vowels-of-a-string.cc
344 Reverse String reverse-string.cc
343 Integer Break integer-break.cc
342 Power of Four power-of-four.cc
341 Flatten Nested List Iterator flatten-nested-list-iterator.cc
340 Longest Substring with At Most K Distinct Characters longest-substring-with-at-most-k-distinct-characters.cc
339 Nested List Weight Sum nested-list-weight-sum.cc
338 Counting Bits counting-bits.cc
337 House Robber III house-robber-iii.cc
336 Palindrome Pairs palindrome-pairs.cc
335 Self Crossing self-crossing.cc
334 Increasing Triplet Subsequence increasing-triplet-subsequence.cc
333 Largest BST Subtree largest-bst-subtree.cc
332 Reconstruct Itinerary reconstruct-itinerary.cc
331 Verify Preorder Serialization of a Binary Tree verify-preorder-serialization-of-a-binary-tree.cc
330 Patching Array patching-array.cc
329 Longest Increasing Path in a Matrix longest-increasing-path-in-a-matrix.cc
328 Odd Even Linked List odd-even-linked-list.cc
327 Count of Range Sum count-of-range-sum.cc
326 Power of Three power-of-three.cc
325 Maximum Size Subarray Sum Equals k maximum-size-subarray-sum-equals-k.cc
324 Wiggle Sort II wiggle-sort-ii.cc
323 Number of Connected Components in an Undirected Graph number-of-connected-components-in-an-undirected-graph.cc
322 Coin Change coin-change.cc
321 Create Maximum Number create-maximum-number.cc
320 Generalized Abbreviation generalized-abbreviation.cc
319 Bulb Switcher bulb-switcher.cc
318 Maximum Product of Word Lengths maximum-product-of-word-lengths.cc
317 Shortest Distance from All Buildings shortest-distance-from-all-buildings.cc
316 Remove Duplicate Letters remove-duplicate-letters.cc
315 Count of Smaller Numbers After Self count-of-smaller-numbers-after-self.cc
314 Binary Tree Vertical Order Traversal binary-tree-vertical-order-traversal.cc
313 Super Ugly Number super-ugly-number.cc
312 Burst Balloons burst-balloons.cc
311 Sparse Matrix Multiplication sparse-matrix-multiplication.cc
310 Minimum Height Trees minimum-height-trees.cc
309 Best Time to Buy and Sell Stock with Cooldown best-time-to-buy-and-sell-stock-with-cooldown.cc
308 Range Sum Query 2D - Mutable range-sum-query-2d-mutable.cc
307 Range Sum Query - Mutable range-sum-query-mutable.cc
306 Additive Number additive-number.cc
305 Number of Islands II number-of-islands-ii.cc
304 Range Sum Query 2D - Immutable range-sum-query-2d-immutable.cc
303 Range Sum Query - Immutable range-sum-query-immutable.cc
302 Smallest Rectangle Enclosing Black Pixels smallest-rectangle-enclosing-black-pixels.cc
301 Remove Invalid Parentheses remove-invalid-parentheses.cc
300 Longest Increasing Subsequence longest-increasing-subsequence.cc
299 Bulls and Cows bulls-and-cows.cc
298 Binary Tree Longest Consecutive Sequence binary-tree-longest-consecutive-sequence.cc
297 Serialize and Deserialize Binary Tree serialize-and-deserialize-binary-tree.cc
296 Best Meeting Point best-meeting-point.cc
295 Find Median from Data Stream find-median-from-data-stream.cc
294 Flip Game II flip-game-ii.cc
293 Flip Game flip-game.cc
292 Nim Game nim-game.cc
291 Word Pattern II word-pattern-ii.cc
290 Word Pattern word-pattern.cc
289 Game of Life game-of-life.cc
288 Unique Word Abbreviation unique-word-abbreviation.cc
287 Find the Duplicate Number find-the-duplicate-number.cc
286 Walls and Gates walls-and-gates.cc
285 Inorder Successor in BST inorder-successor-in-bst.cc
284 Peeking Iterator peeking-iterator.cc
283 Move Zeroes move-zeroes.cc
282 Expression Add Operators expression-add-operators.cc
281 Zigzag Iterator zigzag-iterator.cc
280 Wiggle Sort wiggle-sort.cc
279 Perfect Squares perfect-squares.cc
278 First Bad Version first-bad-version.cc
277 Find the Celebrity find-the-celebrity.cc
276 Paint Fence paint-fence.cc
275 H-Index II h-index-ii.cc
274 H-Index h-index.cc
273 Integer to English Words integer-to-english-words.cc
272 Closest Binary Search Tree Value II closest-binary-search-tree-value-ii.cc
271 Encode and Decode Strings encode-and-decode-strings.cc
270 Closest Binary Search Tree Value closest-binary-search-tree-value.cc
269 Alien Dictionary alien-dictionary.cc
268 Missing Number missing-number.cc
267 Palindrome Permutation II palindrome-permutation-ii.cc
266 Palindrome Permutation palindrome-permutation.cc
265 Paint House II paint-house-ii.cc
264 Ugly Number II ugly-number-ii.cc
263 Ugly Number ugly-number.cc
261 Graph Valid Tree graph-valid-tree.cc
260 Single Number III single-number-iii.cc
259 3Sum Smaller 3sum-smaller.cc
258 Add Digits add-digits.cc
257 Binary Tree Paths binary-tree-paths.cc
256 Paint House paint-house.cc
255 Verify Preorder Sequence in Binary Search Tree verify-preorder-sequence-in-binary-search-tree.cc
254 Factor Combinations factor-combinations.cc
253 Meeting Rooms II meeting-rooms-ii.cc
252 Meeting Rooms meeting-rooms.cc
251 Flatten 2D Vector flatten-2d-vector.cc
250 Count Univalue Subtrees count-univalue-subtrees.cc
249 Group Shifted Strings group-shifted-strings.cc
248 Strobogrammatic Number III strobogrammatic-number-iii.cc
247 Strobogrammatic Number II strobogrammatic-number-ii.cc
246 Strobogrammatic Number strobogrammatic-number.cc
245 Shortest Word Distance III shortest-word-distance-iii.cc
244 Shortest Word Distance II shortest-word-distance-ii.cc
243 Shortest Word Distance shortest-word-distance.cc
242 Valid Anagram valid-anagram.cc
241 Different Ways to Add Parentheses different-ways-to-add-parentheses.cc
240 Search a 2D Matrix II search-a-2d-matrix-ii.cc
239 Sliding Window Maximum sliding-window-maximum.cc
238 Product of Array Except Self product-of-array-except-self.cc
237 Delete Node in a Linked List delete-node-in-a-linked-list.cc
236 Lowest Common Ancestor of a Binary Tree lowest-common-ancestor-of-a-binary-tree.cc
235 Lowest Common Ancestor of a Binary Search Tree lowest-common-ancestor-of-a-binary-search-tree.cc
234 Palindrome Linked List palindrome-linked-list.cc
233 Number of Digit One number-of-digit-one.cc
232 Implement Queue using Stacks implement-queue-using-stacks.cc
231 Power of Two power-of-two.cc
230 Kth Smallest Element in a BST kth-smallest-element-in-a-bst.cc
229 Majority Element II majority-element-ii.cc
228 Summary Ranges summary-ranges.cc
227 Basic Calculator II basic-calculator-ii.cc
226 Invert Binary Tree invert-binary-tree.cc
225 Implement Stack using Queues implement-stack-using-queues.cc
224 Basic Calculator basic-calculator.cc
223 Rectangle Area rectangle-area.cc
222 Count Complete Tree Nodes count-complete-tree-nodes.cc
221 Maximal Square maximal-square.cc
220 Contains Duplicate III contains-duplicate-iii.cc
219 Contains Duplicate II contains-duplicate-ii.cc
218 The Skyline Problem the-skyline-problem.cc
217 Contains Duplicate contains-duplicate.cc
216 Combination Sum III combination-sum-iii.cc
215 Kth Largest Element in an Array kth-largest-element-in-an-array.cc
214 Shortest Palindrome shortest-palindrome.cc
213 House Robber II house-robber-ii.cc
212 Word Search II word-search-ii.cc
210 Course Schedule II course-schedule-ii.cc
209 Minimum Size Subarray Sum minimum-size-subarray-sum.cc
208 Implement Trie (Prefix Tree) implement-trie-prefix-tree.cc
207 Course Schedule course-schedule.cc
206 Reverse Linked List reverse-linked-list.cc
205 Isomorphic Strings isomorphic-strings.cc
204 Count Primes count-primes.cc
203 Remove Linked List Elements remove-linked-list-elements.cc
202 Happy Number happy-number.cc
201 Bitwise AND of Numbers Range bitwise-and-of-numbers-range.cc
200 Number of Islands number-of-islands.cc
199 Binary Tree Right Side View binary-tree-right-side-view.cc
198 House Robber house-robber.cc
191 Number of 1 Bits number-of-1-bits.cc
190 Reverse Bits reverse-bits.cc
189 Rotate Array rotate-array.cc
188 Best Time to Buy and Sell Stock IV best-time-to-buy-and-sell-stock-iv.cc
187 Repeated DNA Sequences repeated-dna-sequences.cc
186 Reverse Words in a String II reverse-words-in-a-string-ii.cc
179 Largest Number largest-number.cc
174 Dungeon Game dungeon-game.cc
173 Binary Search Tree Iterator binary-search-tree-iterator.cc
172 Factorial Trailing Zeroes factorial-trailing-zeroes.cc
171 Excel Sheet Column Number excel-sheet-column-number.cc
170 Two Sum III - Data structure design two-sum-iii-data-structure-design.cc
169 Majority Element majority-element.cc
168 Excel Sheet Column Title excel-sheet-column-title.cc
167 Two Sum II - Input array is sorted two-sum-ii-input-array-is-sorted.cc
166 Fraction to Recurring Decimal fraction-to-recurring-decimal.cc
165 Compare Version Numbers compare-version-numbers.cc
164 Maximum Gap maximum-gap.cc
163 Missing Ranges missing-ranges.cc
162 Find Peak Element find-peak-element.cc
161 One Edit Distance one-edit-distance.cc
160 Intersection of Two Linked Lists intersection-of-two-linked-lists.cc
159 Longest Substring with At Most Two Distinct Characters longest-substring-with-at-most-two-distinct-characters.cc
158 Read N Characters Given Read4 II - Call multiple times read-n-characters-given-read4-ii-call-multiple-times.cc
157 Read N Characters Given Read4 read-n-characters-given-read4.cc
156 Binary Tree Upside Down binary-tree-upside-down.cc
155 Min Stack min-stack.cc
154 Find Minimum in Rotated Sorted Array II find-minimum-in-rotated-sorted-array-ii.cc
153 Find Minimum in Rotated Sorted Array find-minimum-in-rotated-sorted-array.cc
152 Maximum Product Subarray maximum-product-subarray.cc
151 Reverse Words in a String reverse-words-in-a-string.cc
150 Evaluate Reverse Polish Notation evaluate-reverse-polish-notation.cc
149 Max Points on a Line max-points-on-a-line.cc
148 Sort List sort-list.cc
147 Insertion Sort List insertion-sort-list.cc
146 LRU Cache lru-cache.cc
145 Binary Tree Postorder Traversal binary-tree-postorder-traversal.cc
144 Binary Tree Preorder Traversal binary-tree-preorder-traversal.cc
143 Reorder List reorder-list.cc
142 Linked List Cycle II linked-list-cycle-ii.cc
141 Linked List Cycle linked-list-cycle.cc
140 Word Break II word-break-ii.cc
139 Word Break word-break.cc
138 Copy List with Random Pointer copy-list-with-random-pointer.cc
137 Single Number II single-number-ii.cc
136 Single Number single-number.cc
135 Candy candy.cc
134 Gas Station gas-station.cc
133 Clone Graph clone-graph.cc
132 Palindrome Partitioning II palindrome-partitioning-ii.cc
131 Palindrome Partitioning palindrome-partitioning.cc
130 Surrounded Regions surrounded-regions.cc
129 Sum Root to Leaf Numbers sum-root-to-leaf-numbers.cc
128 Longest Consecutive Sequence longest-consecutive-sequence.cc
127 Word Ladder word-ladder.cc
126 Word Ladder II word-ladder-ii.cc
125 Valid Palindrome valid-palindrome.cc
124 Binary Tree Maximum Path Sum binary-tree-maximum-path-sum.cc
123 Best Time to Buy and Sell Stock III best-time-to-buy-and-sell-stock-iii.cc
122 Best Time to Buy and Sell Stock II best-time-to-buy-and-sell-stock-ii.cc
121 Best Time to Buy and Sell Stock best-time-to-buy-and-sell-stock.cc
120 Triangle triangle.cc
119 Pascal's Triangle II pascals-triangle-ii.cc
118 Pascal's Triangle pascals-triangle.cc
117 Populating Next Right Pointers in Each Node II populating-next-right-pointers-in-each-node-ii.cc
116 Populating Next Right Pointers in Each Node populating-next-right-pointers-in-each-node.cc
115 Distinct Subsequences distinct-subsequences.cc
114 Flatten Binary Tree to Linked List flatten-binary-tree-to-linked-list.cc
113 Path Sum II path-sum-ii.cc
112 Path Sum path-sum.cc
111 Minimum Depth of Binary Tree minimum-depth-of-binary-tree.cc
110 Balanced Binary Tree balanced-binary-tree.cc
109 Convert Sorted List to Binary Search Tree convert-sorted-list-to-binary-search-tree.cc
108 Convert Sorted Array to Binary Search Tree convert-sorted-array-to-binary-search-tree.cc
107 Binary Tree Level Order Traversal II binary-tree-level-order-traversal-ii.cc
106 Construct Binary Tree from Inorder and Postorder Traversal construct-binary-tree-from-inorder-and-postorder-traversal.cc
105 Construct Binary Tree from Preorder and Inorder Traversal construct-binary-tree-from-preorder-and-inorder-traversal.cc
104 Maximum Depth of Binary Tree maximum-depth-of-binary-tree.cc
103 Binary Tree Zigzag Level Order Traversal binary-tree-zigzag-level-order-traversal.cc
102 Binary Tree Level Order Traversal binary-tree-level-order-traversal.cc
101 Symmetric Tree symmetric-tree.cc
100 Same Tree same-tree.cc
99 Recover Binary Search Tree recover-binary-search-tree.cc
98 Validate Binary Search Tree validate-binary-search-tree.cc
97 Interleaving String interleaving-string.cc
96 Unique Binary Search Trees unique-binary-search-trees.cc
95 Unique Binary Search Trees II unique-binary-search-trees-ii.cc
94 Binary Tree Inorder Traversal binary-tree-inorder-traversal.cc
93 Restore IP Addresses restore-ip-addresses.cc
92 Reverse Linked List II reverse-linked-list-ii.cc
91 Decode Ways decode-ways.cc
90 Subsets II subsets-ii.cc
89 Gray Code gray-code.cc
88 Merge Sorted Array merge-sorted-array.cc
87 Scramble String scramble-string.cc
86 Partition List partition-list.cc
85 Maximal Rectangle maximal-rectangle.cc
84 Largest Rectangle in Histogram largest-rectangle-in-histogram.cc
83 Remove Duplicates from Sorted List remove-duplicates-from-sorted-list.cc
82 Remove Duplicates from Sorted List II remove-duplicates-from-sorted-list-ii.cc
81 Search in Rotated Sorted Array II search-in-rotated-sorted-array-ii.cc
80 Remove Duplicates from Sorted Array II remove-duplicates-from-sorted-array-ii.cc
79 Word Search word-search.cc
78 Subsets subsets.cc
77 Combinations combinations.cc
76 Minimum Window Substring minimum-window-substring.cc
75 Sort Colors sort-colors.cc
74 Search a 2D Matrix search-a-2d-matrix.cc
73 Set Matrix Zeroes set-matrix-zeroes.cc
72 Edit Distance edit-distance.cc
71 Simplify Path simplify-path.cc
70 Climbing Stairs climbing-stairs.cc
69 Sqrt(x) sqrtx.cc
68 Text Justification text-justification.cc
67 Add Binary add-binary.cc
66 Plus One plus-one.cc
65 Valid Number valid-number.cc
64 Minimum Path Sum minimum-path-sum.cc
63 Unique Paths II unique-paths-ii.cc
62 Unique Paths unique-paths.cc
61 Rotate List rotate-list.cc
60 Permutation Sequence permutation-sequence.cc
59 Spiral Matrix II spiral-matrix-ii.cc
58 Length of Last Word length-of-last-word.cc
57 Insert Interval insert-interval.cc
56 Merge Intervals merge-intervals.cc
55 Jump Game jump-game.cc
54 Spiral Matrix spiral-matrix.cc
53 Maximum Subarray maximum-subarray.cc
52 N-Queens II n-queens-ii.cc
51 N-Queens n-queens.cc
50 Pow(x, n) powx-n.cc
48 Rotate Image rotate-image.cc
47 Permutations II permutations-ii.cc
46 Permutations permutations.cc
45 Jump Game II jump-game-ii.cc
44 Wildcard Matching wildcard-matching.cc
43 Multiply Strings multiply-strings.cc
42 Trapping Rain Water trapping-rain-water.cc
41 First Missing Positive first-missing-positive.cc
40 Combination Sum II combination-sum-ii.cc
39 Combination Sum combination-sum.cc
38 Count and Say count-and-say.cc
37 Sudoku Solver sudoku-solver.cc
36 Valid Sudoku valid-sudoku.cc
35 Search Insert Position search-insert-position.cc
33 Search in Rotated Sorted Array search-in-rotated-sorted-array.cc
32 Longest Valid Parentheses longest-valid-parentheses.cc
31 Next Permutation next-permutation.cc
30 Substring with Concatenation of All Words substring-with-concatenation-of-all-words.cc
29 Divide Two Integers divide-two-integers.cc
28 Implement strStr() implement-strstr.cc
27 Remove Element remove-element.cc
26 Remove Duplicates from Sorted Array remove-duplicates-from-sorted-array.cc
25 Reverse Nodes in k-Group reverse-nodes-in-k-group.cc
24 Swap Nodes in Pairs swap-nodes-in-pairs.cc
23 Merge k Sorted Lists merge-k-sorted-lists.cc
22 Generate Parentheses generate-parentheses.cc
21 Merge Two Sorted Lists merge-two-sorted-lists.cc
20 Valid Parentheses valid-parentheses.cc
19 Remove Nth Node From End of List remove-nth-node-from-end-of-list.cc
18 4Sum 4sum.cc
17 Letter Combinations of a Phone Number letter-combinations-of-a-phone-number.cc
16 3Sum Closest 3sum-closest.cc
15 3Sum 3sum.cc
14 Longest Common Prefix longest-common-prefix.cc
13 Roman to Integer roman-to-integer.cc
12 Integer to Roman integer-to-roman.cc
11 Container With Most Water container-with-most-water.cc
10 Regular Expression Matching regular-expression-matching.cc
9 Palindrome Number palindrome-number.cc
8 String to Integer (atoi) string-to-integer-atoi.cc
7 Reverse Integer reverse-integer.cc
6 ZigZag Conversion zigzag-conversion.cc
5 Longest Palindromic Substring longest-palindromic-substring.cc
4 Median of Two Sorted Arrays median-of-two-sorted-arrays.cc
3 Longest Substring Without Repeating Characters longest-substring-without-repeating-characters.cc
2 Add Two Numbers add-two-numbers.cc
1 Two Sum two-sum.cc
1
2
3
4
5
6
copy($('td:has(.ac) ~ td:nth-child(3) a').map(function(_,e){
var id = $(e).parent().prev().text();
var h=e.href.replace(/htt.*problems/,'/leetcode');h=h.substr(0,h.length-1);
var title=e.textContent, href=e.href, name=h.replace(/.*\//,'');
return '|'+id+'|['+title+']('+href+')|['+name+'.cc]('+name+'.cc)|'
}).toArray().join('\n'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
require 'mechanize'
agent = Mechanize.new
page = agent.get 'https://leetcode.com/accounts/login/'
doc = page.form_with {|form|
form['login'] = 'MaskRay'
form['password'] = getpass
}.submit.parser
total = doc.css('td:nth-child(3)').size
solved = doc.css('td:has(.ac)').size
puts "You have solved #{solved}/#{total} problems."
for a in doc.css('td:nth-child(3) a')
id = a.parent.previous_element.text
href = a['href']
name = href.sub(/\/problems\/(.*)\//, '\1')
title = a.text
puts "|#{id}|[#{title}](#{href})|[#{name}.cc](#{name}.cc)|"
end

Ko-Aluru suffix array construction algorithm

Suffix array是解决string search问题的一个工具,它是一个字串所有后缀的排序。

线性时间的构建算法主要有Kärkkäinen-Sanders(1)、Ko-Aluru(2)、KSP三种,其中KSP算法使用了类似suffix tree的构建方式,Kärkkäinen-Sanders算法时间复杂度的递推式为,通常认为性能不如的Ko-Aluru。

按照3的注记,借鉴4对LMS substring递归排序使用的方法, 对原始的Ko-Aluru算法进行改动以简化内存使用和提升性能。 我的实现在字串和suffix array外仅使用两个数组:计数排序使用的桶和一个表示L/S类型的数组, 反映了Ko-Aluru算法能达到和5同等的精简内存占用。

Read More