Eertree: Difference between revisions

Content added Content deleted

Inline

@@ Line 18: / Line 18: @@
 * &nbsp; [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#}}==