65 lines
1.2 KiB
Text
65 lines
1.2 KiB
Text
T Node
|
||
Int length
|
||
Int suffix
|
||
[Char = Int] edges
|
||
|
||
F (length, suffix = 0)
|
||
.length = length
|
||
.suffix = suffix
|
||
|
||
-V oddRoot = 1
|
||
|
||
F eertree(s)
|
||
V tree = [Node(0, :oddRoot), Node(-1, :oddRoot)]
|
||
V suffix = :oddRoot
|
||
L(c) s
|
||
V i = L.index
|
||
V n = suffix
|
||
Int k
|
||
L
|
||
k = tree[n].length
|
||
V b = i - k - 1
|
||
I b >= 0 & s[b] == c
|
||
L.break
|
||
n = tree[n].suffix
|
||
|
||
V? edge = tree[n].edges.find(c)
|
||
I edge != N
|
||
suffix = edge
|
||
L.continue
|
||
|
||
suffix = tree.len
|
||
tree [+]= Node(k + 2)
|
||
tree[n].edges[c] = suffix
|
||
I tree[suffix].length == 1
|
||
tree[suffix].suffix = 0
|
||
L.continue
|
||
|
||
L
|
||
n = tree[n].suffix
|
||
V b = i - tree[n].length - 1
|
||
I b >= 0 & s[b] == c
|
||
L.break
|
||
|
||
tree[suffix].suffix = tree[n].edges[c]
|
||
|
||
R tree
|
||
|
||
F subPalindromes(tree)
|
||
[String] s
|
||
|
||
F children(Int n, String =p) -> N
|
||
L(c, n) @tree[n].edges
|
||
p = c‘’p‘’c
|
||
@s [+]= p
|
||
@children(n, p)
|
||
|
||
children(0, ‘’)
|
||
L(c, n) tree[1].edges
|
||
s [+]= c
|
||
children(n, c)
|
||
|
||
R s
|
||
|
||
V tree = eertree(‘eertree’)
|
||
print(subPalindromes(tree))
|