Eertree: Difference between revisions
Added 11l
(Added Wren) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 18:
* [https://arxiv.org/abs/1506.04862 Cornell University Library, Computer Science, Data Structures and Algorithms ───► EERTREE: An Efficient Data Structure for Processing Palindromes in Strings].
<br><br>
=={{header|11l}}==
{{trans|D}}
<lang 11l>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
I c C tree[n].edges
suffix = tree[n].edges[c]
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))</lang>
{{out}}
<pre>
[ee, e, r, t, rtr, ertre, eertree]
</pre>
=={{header|C sharp|C#}}==
| |||