Eertree: Difference between revisions
(Added Wren) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 18: | 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]. |
* [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> |
<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#}}== |
=={{header|C sharp|C#}}== |
Revision as of 02:37, 9 June 2021
You are encouraged to solve this task according to the task description, using any language you may know.
An eertree is a data structure designed for efficient processing of certain palindrome tasks, for instance counting the number of sub-palindromes in an input string.
The data structure has commonalities to both tries and suffix trees. See links below.
- Task
Construct an eertree for the string "eertree", then output all sub-palindromes by traversing the tree.
- See also
- Wikipedia entry: trie.
- Wikipedia entry: suffix tree
- Cornell University Library, Computer Science, Data Structures and Algorithms ───► EERTREE: An Efficient Data Structure for Processing Palindromes in Strings.
11l
<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>
- Output:
[ee, e, r, t, rtr, ertre, eertree]
C#
<lang csharp>using System; using System.Collections.Generic;
namespace Eertree {
class Node { public Node(int length) { this.Length = length; // empty or this.Edges = new Dictionary<char, int>(); }
public Node(int length, Dictionary<char, int> edges, int suffix) { this.Length = length; this.Edges = edges; this.Suffix = suffix; }
public int Length { get; set; } public Dictionary<char, int> Edges { get; set; } public int Suffix { get; set; } }
class Program { const int EVEN_ROOT = 0; const int ODD_ROOT = 1;
static List<Node> Eertree(string s) { List<Node> tree = new List<Node> { //new Node(0, null, ODD_ROOT), or new Node(0, new Dictionary<char, int>(), ODD_ROOT), //new Node(-1, null, ODD_ROOT) or new Node(-1, new Dictionary<char, int>(), ODD_ROOT) }; int suffix = ODD_ROOT; int n, k; for (int i = 0; i < s.Length; i++) { char c = s[i]; for (n = suffix; ; n = tree[n].Suffix) { k = tree[n].Length; int b = i - k - 1; if (b >= 0 && s[b] == c) { break; } } if (tree[n].Edges.ContainsKey(c)) { suffix = tree[n].Edges[c]; continue; } suffix = tree.Count; tree.Add(new Node(k + 2)); tree[n].Edges[c] = suffix; if (tree[suffix].Length == 1) { tree[suffix].Suffix = 0; continue; } while (true) { n = tree[n].Suffix; int b = i - tree[n].Length - 1; if (b >= 0 && s[b] == c) { break; } } tree[suffix].Suffix = tree[n].Edges[c]; } return tree; }
static List<string> SubPalindromes(List<Node> tree) { List<string> s = new List<string>(); SubPalindromes_children(0, "", tree, s); foreach (var c in tree[1].Edges.Keys) { int m = tree[1].Edges[c]; string ct = c.ToString(); s.Add(ct); SubPalindromes_children(m, ct, tree, s); } return s; }
static void SubPalindromes_children(int n, string p, List<Node> tree, List<string> s) { foreach (var c in tree[n].Edges.Keys) { int m = tree[n].Edges[c]; string p1 = c + p + c; s.Add(p1); SubPalindromes_children(m, p1, tree, s); } }
static void Main(string[] args) { List<Node> tree = Eertree("eertree"); List<string> result = SubPalindromes(tree); string listStr = string.Join(", ", result); Console.WriteLine("[{0}]", listStr); } }
}</lang>
- Output:
[ee, e, r, t, rtr, ertre, eertree]
C++
<lang cpp>#include <iostream>
- include <functional>
- include <map>
- include <vector>
struct Node {
int length; std::map<char, int> edges; int suffix;
Node(int l) : length(l), suffix(0) { /* empty */ }
Node(int l, const std::map<char, int>& m, int s) : length(l), edges(m), suffix(s) { /* empty */ }
};
constexpr int evenRoot = 0; constexpr int oddRoot = 1;
std::vector<Node> eertree(const std::string& s) {
std::vector<Node> tree = { Node(0, {}, oddRoot), Node(-1, {}, oddRoot) }; int suffix = oddRoot; int n, k;
for (size_t i = 0; i < s.length(); ++i) { char c = s[i]; for (n = suffix; ; n = tree[n].suffix) { k = tree[n].length; int b = i - k - 1; if (b >= 0 && s[b] == c) { break; } }
auto it = tree[n].edges.find(c); auto end = tree[n].edges.end(); if (it != end) { suffix = it->second; continue; } suffix = tree.size(); tree.push_back(Node(k + 2)); tree[n].edges[c] = suffix; if (tree[suffix].length == 1) { tree[suffix].suffix = 0; continue; } while (true) { n = tree[n].suffix; int b = i - tree[n].length - 1; if (b >= 0 && s[b] == c) { break; } } tree[suffix].suffix = tree[n].edges[c]; }
return tree;
}
std::vector<std::string> subPalindromes(const std::vector<Node>& tree) {
std::vector<std::string> s;
std::function<void(int, std::string)> children; children = [&children, &tree, &s](int n, std::string p) { auto it = tree[n].edges.cbegin(); auto end = tree[n].edges.cend(); for (; it != end; it = std::next(it)) { auto c = it->first; auto m = it->second;
std::string pl = c + p + c; s.push_back(pl); children(m, pl); } }; children(0, "");
auto it = tree[1].edges.cbegin(); auto end = tree[1].edges.cend(); for (; it != end; it = std::next(it)) { auto c = it->first; auto n = it->second;
std::string ct(1, c); s.push_back(ct);
children(n, ct); }
return s;
}
int main() {
using namespace std;
auto tree = eertree("eertree"); auto pal = subPalindromes(tree);
auto it = pal.cbegin(); auto end = pal.cend();
cout << "["; if (it != end) { cout << it->c_str(); it++; } while (it != end) { cout << ", " << it->c_str(); it++; } cout << "]" << endl;
return 0;
}</lang>
- Output:
[ee, e, r, t, rtr, ertre, eertree]
D
<lang D>import std.array; import std.stdio;
void main() {
auto tree = eertree("eertree"); writeln(subPalindromes(tree));
}
struct Node {
int length; int[char] edges; int suffix;
}
const evenRoot = 0; const oddRoot = 1;
Node[] eertree(string s) {
Node[] tree = [ Node(0, null, oddRoot), Node(-1, null, oddRoot), ]; int suffix = oddRoot; int n, k; foreach (i, c; s) { for (n=suffix; ; n=tree[n].suffix) { k = tree[n].length; int b = i-k-1; if (b>=0 && s[b]==c) { break; } } if (c in tree[n].edges) { suffix = tree[n].edges[c]; continue; } suffix = tree.length; tree ~= Node(k+2); tree[n].edges[c] = suffix; if (tree[suffix].length == 1) { tree[suffix].suffix = 0; continue; } while (true) { n = tree[n].suffix; int b = i-tree[n].length-1; if (b>=0 && s[b]==c) { break; } } tree[suffix].suffix = tree[n].edges[c]; } return tree;
}
auto subPalindromes(Node[] tree) {
auto s = appender!(string[]); void children(int n, string p) { foreach (c, n; tree[n].edges) { p = c ~ p ~ c; s ~= p; children(n, p); } } children(0, ""); foreach (c, n; tree[1].edges) { string ct = [c].idup; s ~= ct; children(n, ct); } return s.data;
}</lang>
- Output:
["ee", "e", "r", "t", "rtr", "ertre", "eertree"]
Go
<lang go>package main
import "fmt"
func main() {
tree := eertree([]byte("eertree")) fmt.Println(subPalindromes(tree))
}
type edges map[byte]int
type node struct {
length int edges suffix int
}
const evenRoot = 0 const oddRoot = 1
func eertree(s []byte) []node {
tree := []node{ evenRoot: {length: 0, suffix: oddRoot, edges: edges{}}, oddRoot: {length: -1, suffix: oddRoot, edges: edges{}}, } suffix := oddRoot var n, k int for i, c := range s { for n = suffix; ; n = tree[n].suffix { k = tree[n].length if b := i - k - 1; b >= 0 && s[b] == c { break } } if e, ok := tree[n].edges[c]; ok { suffix = e continue } suffix = len(tree) tree = append(tree, node{length: k + 2, edges: edges{}}) tree[n].edges[c] = suffix if tree[suffix].length == 1 { tree[suffix].suffix = 0 continue } for { n = tree[n].suffix if b := i - tree[n].length - 1; b >= 0 && s[b] == c { break } } tree[suffix].suffix = tree[n].edges[c] } return tree
}
func subPalindromes(tree []node) (s []string) {
var children func(int, string) children = func(n int, p string) { for c, n := range tree[n].edges { c := string(c) p := c + p + c s = append(s, p) children(n, p) } } children(0, "") for c, n := range tree[1].edges { c := string(c) s = append(s, c) children(n, c) } return
}</lang>
- Output:
[ee e r t rtr ertre eertree]
Java
<lang Java>import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map;
public class Eertree {
public static void main(String[] args) { List<Node> tree = eertree("eertree"); List<String> result = subPalindromes(tree); System.out.println(result); }
private static class Node { int length; Map<Character, Integer> edges = new HashMap<>(); int suffix;
public Node(int length) { this.length = length; }
public Node(int length, Map<Character, Integer> edges, int suffix) { this.length = length; this.edges = edges != null ? edges : new HashMap<>(); this.suffix = suffix; } }
private static final int EVEN_ROOT = 0; private static final int ODD_ROOT = 1;
private static List<Node> eertree(String s) { List<Node> tree = new ArrayList<>(); tree.add(new Node(0, null, ODD_ROOT)); tree.add(new Node(-1, null, ODD_ROOT)); int suffix = ODD_ROOT; int n, k; for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); for (n = suffix; ; n = tree.get(n).suffix) { k = tree.get(n).length; int b = i - k - 1; if (b >= 0 && s.charAt(b) == c) { break; } } if (tree.get(n).edges.containsKey(c)) { suffix = tree.get(n).edges.get(c); continue; } suffix = tree.size(); tree.add(new Node(k + 2)); tree.get(n).edges.put(c, suffix); if (tree.get(suffix).length == 1) { tree.get(suffix).suffix = 0; continue; } while (true) { n = tree.get(n).suffix; int b = i - tree.get(n).length - 1; if (b >= 0 && s.charAt(b) == c) { break; } } tree.get(suffix).suffix = tree.get(n).edges.get(c); } return tree; }
private static List<String> subPalindromes(List<Node> tree) { List<String> s = new ArrayList<>(); subPalindromes_children(0, "", tree, s); for (Map.Entry<Character, Integer> cm : tree.get(1).edges.entrySet()) { String ct = String.valueOf(cm.getKey()); s.add(ct); subPalindromes_children(cm.getValue(), ct, tree, s); } return s; }
// nested methods are a pain, even if lambdas make that possible for Java private static void subPalindromes_children(final int n, final String p, final List<Node> tree, List<String> s) { for (Map.Entry<Character, Integer> cm : tree.get(n).edges.entrySet()) { Character c = cm.getKey(); Integer m = cm.getValue(); String pl = c + p + c; s.add(pl); subPalindromes_children(m, pl, tree, s); } }
}</lang>
- Output:
[ee, r, t, rtr, ertre, eertree, e]
Julia
<lang julia>mutable struct Node
edges::Dict{Char, Node} link::Union{Node, Missing} sz::Int Node() = new(Dict(), missing, 0)
end
sizednode(x) = (n = Node(); n.sz = x; n)
function eertree(str)
nodes = Vector{Node}() oddroot = sizednode(-1) evenroot = sizednode(0) oddroot.link = evenroot evenroot.link = oddroot S = "0" maxsuffix = evenroot
function maxsuffixpal(startnode,a::Char) # Traverse the suffix-palindromes of tree looking for equality with a u = startnode i = length(S) k = u.sz while u !== oddroot && S[i - k] != a if u === u.link throw("circular reference above oddroot") end u = u.link k = u.sz end u end
function addchar(a::Char) Q = maxsuffixpal(maxsuffix, a) creatednode = !haskey(Q.edges, a) if creatednode P = sizednode(Q.sz + 2) push!(nodes, P) if P.sz == 1 P.link = evenroot else P.link = maxsuffixpal(Q.link, a).edges[a] end Q.edges[a] = P # adds edge (Q, P) end maxsuffix = Q.edges[a] # P becomes the new maxsuffix S *= string(a) creatednode end
function getsubpalindromes() result = Vector{String}() getsubpalindromes(oddroot, [oddroot], "", result) getsubpalindromes(evenroot, [evenroot], "", result) result end
function getsubpalindromes(nd, nodestohere, charstohere, result) for (lnkname, nd2) in nd.edges getsubpalindromes(nd2, vcat(nodestohere, nd2), charstohere * lnkname, result) end if nd !== oddroot && nd !== evenroot assembled = reverse(charstohere) * (nodestohere[1] === evenroot ? charstohere : charstohere[2:end]) push!(result, assembled) end end
println("Results of processing string \"$str\":") for c in str addchar(c) end println("Number of sub-palindromes: ", length(nodes)) println("Sub-palindromes: ", getsubpalindromes())
end
eertree("eertree")
</lang>
- Output:
Results of processing string "eertree": Number of sub-palindromes: 7 Sub-palindromes: ["e", "r", "eertree", "ertre", "rtr", "t", "ee"]
Kotlin
<lang scala>// version 1.1.4
class Node {
val edges = mutableMapOf<Char, Node>() // edges (or forward links) var link: Node? = null // suffix link (backward links) var len = 0 // the length of the node
}
class Eertree(str: String) {
val nodes = mutableListOf<Node>()
private val rto = Node() // odd length root node, or node -1 private val rte = Node() // even length root node, or node 0 private val s = StringBuilder("0") // accumulated input string, T = S[1..i] private var maxSufT = rte // maximum suffix of tree T
init { // Initialize and build the tree rte.link = rto rto.link = rte rto.len = -1 rte.len = 0 for (ch in str) add(ch) }
private fun getMaxSuffixPal(startNode: Node, a: Char): Node { // We traverse the suffix-palindromes of T in the order of decreasing length. // For each palindrome we read its length k and compare T[i-k] against a // until we get an equality or arrive at the -1 node. var u = startNode val i = s.length var k = u.len while (u !== rto && s[i - k - 1] != a) { if (u === u.link!!) throw RuntimeException("Infinite loop detected") u = u.link!! k = u.len } return u }
private fun add(a: Char): Boolean { // We need to find the maximum suffix-palindrome P of Ta // Start by finding maximum suffix-palindrome Q of T. // To do this, we traverse the suffix-palindromes of T // in the order of decreasing length, starting with maxSuf(T) val q = getMaxSuffixPal(maxSufT, a)
// We check Q to see whether it has an outgoing edge labeled by a. val createANewNode = a !in q.edges.keys
if (createANewNode) { // We create the node P of length Q + 2 val p = Node() nodes.add(p) p.len = q.len + 2 if (p.len == 1) { // if P = a, create the suffix link (P, 0) p.link = rte } else { // It remains to create the suffix link from P if |P|>1. Just // continue traversing suffix-palindromes of T starting with the // the suffix link of Q. p.link = getMaxSuffixPal(q.link!!, a).edges[a] }
// create the edge (Q, P) q.edges[a] = p }
// P becomes the new maxSufT maxSufT = q.edges[a]!!
// Store accumulated input string s.append(a)
return createANewNode }
fun getSubPalindromes(): List<String> { // Traverse tree to find sub-palindromes val result = mutableListOf<String>() // Odd length words getSubPalindromes(rto, listOf(rto), "", result) // Even length words getSubPalindromes(rte, listOf(rte), "", result) return result }
private fun getSubPalindromes(nd: Node, nodesToHere: List<Node>, charsToHere: String, result: MutableList<String>) { // Each node represents a palindrome, which can be reconstructed // by the path from the root node to each non-root node.
// Traverse all edges, since they represent other palindromes for ((lnkName, nd2) in nd.edges) { getSubPalindromes(nd2, nodesToHere + nd2, charsToHere + lnkName, result) }
// Reconstruct based on charsToHere characters. if (nd !== rto && nd !== rte) { // Don't print for root nodes val assembled = charsToHere.reversed() + if (nodesToHere[0] === rte) // Even string charsToHere else // Odd string charsToHere.drop(1) result.add(assembled) } }
}
fun main(args: Array<String>) {
val str = "eertree" println("Processing string '$str'") val eertree = Eertree(str) println("Number of sub-palindromes: ${eertree.nodes.size}") val result = eertree.getSubPalindromes() println("Sub-palindromes: $result")
}</lang>
- Output:
Processing string 'eertree' Number of sub-palindromes: 7 Sub-palindromes: [e, r, eertree, ertre, rtr, t, ee]
M2000 Interpreter
<lang M2000 Interpreter> If Version<9.5 Then exit If Version=9.5 And Revision<2 Then Exit Class Node {
inventory myedges length, suffix=0 Function edges(s$) { =-1 : if exist(.myedges, s$) then =eval(.myedges) } Module edges_append (a$, where) { Append .myedges, a$:=where }
Class:
Module Node(.length) { Read ? .suffix, .myedges }
} function eertree(s$) {
Const evenRoot=0, oddRoot=1 Inventory Tree= oddRoot:=Node(-1,1),evenRoot:=Node(0,1) k=0 suffix=oddRoot for i=0 to len(s$)-1 { c$=mid$(s$,i+1,1) n=suffix Do { k=tree(n).length b=i-k-1 if b>=0 then if mid$(s$,b+1,1)=c$ Then exit n =tree(n).suffix } Always e=tree(n).edges(c$) if e>=0 then suffix=e :continue suffix=len(Tree) Append Tree, len(Tree):=Node(k+2) Tree(n).edges_append c$, suffix If tree(suffix).length=1 then tree(suffix).suffix=0 : continue Do { n=tree(n).suffix b=i-tree(n).length-1 if b>0 Then If mid$(s$, b+1,1)=c$ then exit } Always e=tree(n).edges(c$) if e>=0 then tree(suffix).suffix=e
} =tree
} children=lambda (s, tree, n, root$="")->{
L=Len(tree(n).myEdges) if L=0 then =s : exit L-- For i=0 to L { c=tree(n).myEdges c$=Eval$(c, i) ' read keys at position i nxt=c(i!) ' read value using position p$ = if$(n=1 -> c$, c$+root$+c$) append s, (p$,) \\ better use lambda() and not children() \\ for recursion when we copy this lambda to other identifier. s = lambda(s, tree, nxt, p$) } = s }
aString=Lambda ->{
Push Quote$(Letter$)
} aLine=Lambda ->{
Shift 2 ' swap two top stack items if stackitem$()="" then { Drop} Else Push letter$+", "+Letter$
} Palindromes$=Lambda$ children, aString, aLine (Tree)-> {
="("+children(children((,), Tree, 0), Tree, 1)#Map(aString)#Fold$(aline,"")+")" }
Print Palindromes$(eertree("eertree")) </lang>
- Output:
("ee", "e", "r", "t", "rtr", "ertre", "eertree")
Nim
<lang Nim>import algorithm, strformat, strutils, tables
type
Node = ref object edges: Table[char, Node] # Edges (forward links). link: Node # Suffix link (backward link). len: int # Length of the node.
Eertree = object nodes: seq[Node] rto: Node # Odd length root node or node -1. rte: Node # Even length root node or node 0.Node str: string # Accumulated input string. maxSuf: Node # Maximum suffix.
- ---------------------------------------------------------------------------------------------------
func initEertree(): Eertree =
## Create and initialize an eertree. result = Eertree(rto: Node(len: - 1), rte: Node(len: 0)) result.rto.link = result.rto result.rte.link = result.rto result.str = "0" result.maxSuf = result.rte
- ---------------------------------------------------------------------------------------------------
func getMaxSuffixPal(tree: Eertree; startNode: Node; ch: char): Node =
## We traverse the suffix-palindromes of "tree" in the order of decreasing length. ## For each palindrome we read its length "k" and compare "tree[i-k]" against "ch" ## until we get an equality or arrive at the -1 node.
result = startNode let i = tree.str.high while result != tree.rto and tree.str[i - result.len] != ch: doAssert(result != result.link, "circular reference above odd root") result = result.link
- ---------------------------------------------------------------------------------------------------
func add(tree: var Eertree; ch: char): bool =
## We need to find the maximum suffix-palindrome P of Ta. ## Start by finding maximum suffix-palindrome Q of T. ## To do this, we traverse the suffix-palindromes of T ## in the order of decreasing length, starting with maxSuf(T).
let q = tree.getMaxSuffixPal(tree.maxSuf, ch)
# We check "q" to see whether it has an outgoing edge labeled by "ch". result = ch notin q.edges
if result: # We create the node "p" of length "q.len + 2" let p = Node() tree.nodes.add(p) p.len = q.len + 2 if p.len == 1: # If p = ch, create the suffix link (p, 0). p.link = tree.rte else: # It remains to create the suffix link from "p" if "|p|>1". Just continue # traversing suffix-palindromes of T starting with the suffix link of "q". p.link = tree.getMaxSuffixPal(q.link, ch).edges[ch] # Create the edge "(q, p)". q.edges[ch] = p
# "p" becomes the new maxSuf. tree.maxSuf = q.edges[ch]
# Store accumulated input string. tree.str.add(ch)
- ---------------------------------------------------------------------------------------------------
func getSubPalindromes(tree: Eertree; node: Node;
nodesToHere: seq[Node]; charsToHere: string; result: var seq[string]) = ## Each node represents a palindrome, which can be reconstructed ## by the path from the root node to each non-root node.
# Traverse all edges, since they represent other palindromes. for linkName, node2 in node.edges.pairs: tree.getSubPalindromes(node2, nodesToHere & node2, charsToHere & linkName, result)
# Reconstruct based on charsToHere characters. if node notin [tree.rto, tree.rte]: # Don’t print for root nodes. let assembled = reversed(charsTohere).join() & (if nodesToHere[0] == tree.rte: charsToHere else: charsToHere[1..^1]) result.add(assembled)
- ---------------------------------------------------------------------------------------------------
func getSubPalindromes(tree: Eertree): seq[string] =
## Traverse tree to find sub-palindromes.
# Odd length words tree.getSubPalindromes(tree.rto, @[tree.rto], "", result) # Even length words tree.getSubPalindromes(tree.rte, @[tree.rte], "", result)
- ———————————————————————————————————————————————————————————————————————————————————————————————————
when isMainModule:
const Str = "eertree" echo fmt"Processing string: '{Str}'" var eertree = initEertree() for ch in Str: discard eertree.add(ch) echo fmt"Number of sub-palindromes: {eertree.nodes.len}" let result = eertree.getSubPalindromes() echo fmt"Sub-palindromes: {result.join("", "")}"</lang>
- Output:
Processing string: 'eertree' Number of sub-palindromes: 7 Sub-palindromes: r, eertree, ertre, rtr, t, e, ee
Objeck
<lang objeck>use Collection.Generic;
class Eertree {
function : Main(args : String[]) ~ Nil { tree := GetEertree("eertree"); Show(SubPalindromes(tree)); }
function : GetEertree(s : String) ~ Vector<Node> { tree := Vector->New()<Node>; tree->AddBack(Node->New(0, Nil, 1)); tree->AddBack(Node->New(-1, Nil, 1)); suffix := 1; n : Int; k : Int; for(i := 0; i < s->Size(); ++i;) { c := s->Get(i);
done := false; for (j := suffix; <>done; j := tree->Get(j)->GetSuffix();) { k := tree->Get(j)->GetLength(); b := i - k - 1; if (b >= 0 & s->Get(b) = c) { n := j; done := true; }; }; skip := false; if (tree->Get(n)->GetEdges()->Has(c)) { suffix := tree->Get(n)->GetEdges()->Find(c)->Get(); skip := true; };
if(<>skip) { suffix := tree->Size(); tree->AddBack(Node->New(k + 2)); tree->Get(n)->GetEdges()->Insert(c, suffix); if (tree->Get(suffix)->GetLength() = 1) { tree->Get(suffix)->SetSuffix(0); skip := true; };
if(<>skip) { done := false; while (<>done) { n := tree->Get(n)->GetSuffix(); b := i - tree->Get(n)->GetLength() - 1; if (b >= 0 & s->Get(b) = c) { done := true; }; }; tree->Get(suffix)->SetSuffix(tree->Get(n)->GetEdges()->Find(c)->Get()); }; }; };
return tree; }
function : SubPalindromes(tree : Vector<Node>) ~ Vector<String> { s := Vector->New()<String>; SubPalindromesChildren(0, "", tree, s);
keys := tree->Get(1)->GetEdges()->GetKeys()<CharHolder>; each(k : keys) { key := keys->Get(k); str := key->Get()->ToString(); s->AddBack(str); value := tree->Get(1)->GetEdges()->Find(key)->As(IntHolder)->Get(); SubPalindromesChildren(value, str, tree, s); };
return s; }
function : SubPalindromesChildren(n : Int, p : String, tree : Vector<Node>, s : Vector<String>) ~ Nil { keys := tree->Get(n)->GetEdges()->GetKeys()<CharHolder>; each(k : keys) { key := keys->Get(k); c := key->Get(); value := tree->Get(n)->GetEdges()->Find(key)->As(IntHolder)->Get(); str := ""; str += c; str += p; str += c; s->AddBack(str); SubPalindromesChildren(value, str, tree, s); }; }
function : Show(result : Vector<String>) ~ Nil { out := "["; each(i : result) { out += result->Get(i); if(i + 1 < result->Size()) { out += ", "; }; }; out += "]"; out->PrintLine(); }
}
class Node {
@length : Int; @edges : Map<CharHolder, IntHolder>; @suffix : Int;
New(length : Int, edges : Map<CharHolder, IntHolder>, suffix : Int) { @length := length; @edges := edges <> Nil ? edges : Map->New()<CharHolder, IntHolder>; @suffix := suffix; }
New(length : Int) { @length := length; @edges := Map->New()<CharHolder, IntHolder>; }
method : public : GetLength() ~ Int { return @length; }
method : public : GetSuffix() ~ Int { return @suffix; }
method : public : SetSuffix(suffix : Int) ~ Nil { @suffix := suffix; }
method : public : GetEdges() ~ Map<CharHolder, IntHolder> { return @edges; }
}</lang>
- Output:
[ee, e, r, t, rtr, ertre, eertree]
Perl
<lang perl>$str = "eertree";
for $n (1 .. length($str)) {
for $m (1 .. length($str)) { $strrev = ""; $strpal = substr($str, $n-1, $m); if ($strpal ne "") { for $p (reverse 1 .. length($strpal)) { $strrev .= substr($strpal, $p-1, 1); } ($strpal eq $strrev) and push @pal, $strpal; } }
}
print join ' ', grep {not $seen{$_}++} @pal, "\n";</lang>
- Output:
e ee eertree ertre r rtr t
Phix
If you use this in anger it may be wise to replace {string chars, sequence next} with a dictionary, which can obviously be either a new dictionary for each node, or perhaps better a single/per tree dictionary keyed on {n,ch}. <lang Phix>enum LEN,SUFF,CHARS,NEXT
function node(integer len, suffix=1, string chars="", sequence next={})
return {len,suffix,chars,next} -- must match above enum!
end function
function eertree(string s) sequence tree = {node(-1), -- odd lengths
node(0)} -- even lengths
integer suff = 2 -- max suffix palindrome
for i=1 to length(s) do integer cur = suff, curlen, ch = s[i], k while (true) do curlen = tree[cur][LEN] k = i-1-curlen if k>=1 and s[k]==ch then exit end if cur = tree[cur][SUFF] end while k = find(ch,tree[cur][CHARS]) if k then suff = tree[cur][NEXT][k] else tree = append(tree,node(curlen+2)) suff = length(tree) tree[cur][CHARS] &= ch tree[cur][NEXT] &= suff
if tree[suff][LEN]==1 then tree[suff][SUFF] = 2 else while (true) do cur = tree[cur][SUFF] curlen = tree[cur][LEN] k = i-1-curlen if k>=0 and s[k]==ch then k = find(ch,tree[cur][CHARS]) if k then tree[suff][SUFF] = tree[cur][NEXT][k] end if exit end if end while end if end if end for return tree
end function
function children(sequence s, tree, integer n, string root="")
for i=1 to length(tree[n][CHARS]) do integer c = tree[n][CHARS][i], nxt = tree[n][NEXT][i] string p = iff(n=1 ? c&"" : c&root&c) s = append(s, p) s = children(s, tree, nxt, p) end for return s
end function
procedure main()
sequence tree = eertree("eertree") puts(1,"tree:\n") for i=1 to length(tree) do sequence ti = tree[i] ti[NEXT] = sprint(ti[NEXT]) printf(1,"[%d]: len:%2d suffix:%d chars:%-5s next:%s\n",i&ti) end for puts(1,"\n")
-- odd then even lengths: ?children(children(s,tree,1), tree, 2)
end procedure main()</lang>
- Output:
The tree matches Fig 1 in the pdf linked above.
tree: [1]: len:-1 suffix:1 chars:ert next:{3,5,6} [2]: len: 0 suffix:1 chars:e next:{4} [3]: len: 1 suffix:2 chars: next:{} [4]: len: 2 suffix:3 chars: next:{} [5]: len: 1 suffix:2 chars: next:{} [6]: len: 1 suffix:2 chars:r next:{7} [7]: len: 3 suffix:5 chars:e next:{8} [8]: len: 5 suffix:3 chars:e next:{9} [9]: len: 7 suffix:4 chars: next:{} {"e","r","t","rtr","ertre","eertree","ee"}
Python
<lang python>#!/bin/python from __future__ import print_function
class Node(object): def __init__(self): self.edges = {} # edges (or forward links) self.link = None # suffix link (backward links) self.len = 0 # the length of the node
class Eertree(object): def __init__(self): self.nodes = [] # two initial root nodes self.rto = Node() #odd length root node, or node -1 self.rte = Node() #even length root node, or node 0
# Initialize empty tree self.rto.link = self.rte.link = self.rto; self.rto.len = -1 self.rte.len = 0 self.S = [0] # accumulated input string, T=S[1..i] self.maxSufT = self.rte # maximum suffix of tree T
def get_max_suffix_pal(self, startNode, a): # We traverse the suffix-palindromes of T in the order of decreasing length. # For each palindrome we read its length k and compare T[i-k] against a # until we get an equality or arrive at the -1 node. u = startNode i = len(self.S) k = u.len while id(u) != id(self.rto) and self.S[i - k - 1] != a: assert id(u) != id(u.link) #Prevent infinte loop u = u.link k = u.len
return u
def add(self, a):
# We need to find the maximum suffix-palindrome P of Ta # Start by finding maximum suffix-palindrome Q of T. # To do this, we traverse the suffix-palindromes of T # in the order of decreasing length, starting with maxSuf(T) Q = self.get_max_suffix_pal(self.maxSufT, a)
# We check Q to see whether it has an outgoing edge labeled by a. createANewNode = not a in Q.edges
if createANewNode: # We create the node P of length Q+2 P = Node() self.nodes.append(P) P.len = Q.len + 2 if P.len == 1: # if P = a, create the suffix link (P,0) P.link = self.rte else: # It remains to create the suffix link from P if |P|>1. Just # continue traversing suffix-palindromes of T starting with the suffix # link of Q. P.link = self.get_max_suffix_pal(Q.link, a).edges[a]
# create the edge (Q,P) Q.edges[a] = P
#P becomes the new maxSufT self.maxSufT = Q.edges[a]
#Store accumulated input string self.S.append(a)
return createANewNode
def get_sub_palindromes(self, nd, nodesToHere, charsToHere, result): #Each node represents a palindrome, which can be reconstructed #by the path from the root node to each non-root node.
#Traverse all edges, since they represent other palindromes for lnkName in nd.edges: nd2 = nd.edges[lnkName] #The lnkName is the character used for this edge self.get_sub_palindromes(nd2, nodesToHere+[nd2], charsToHere+[lnkName], result)
#Reconstruct based on charsToHere characters. if id(nd) != id(self.rto) and id(nd) != id(self.rte): #Don't print for root nodes tmp = "".join(charsToHere) if id(nodesToHere[0]) == id(self.rte): #Even string assembled = tmp[::-1] + tmp else: #Odd string assembled = tmp[::-1] + tmp[1:] result.append(assembled)
if __name__=="__main__": st = "eertree" print ("Processing string", st) eertree = Eertree() for ch in st: eertree.add(ch)
print ("Number of sub-palindromes:", len(eertree.nodes))
#Traverse tree to find sub-palindromes result = [] eertree.get_sub_palindromes(eertree.rto, [eertree.rto], [], result) #Odd length words eertree.get_sub_palindromes(eertree.rte, [eertree.rte], [], result) #Even length words print ("Sub-palindromes:", result)</lang>
- Output:
Processing string eertree Number of sub-palindromes: 7 Sub-palindromes: ['r', 'e', 'eertree', 'ertre', 'rtr', 't', 'ee']
Racket
<lang racket>#lang racket (struct node (edges ; edges (or forward links)
link ; suffix link (backward links) len) ; the length of the node #:mutable)
(define (new-node link len) (node (make-hash) link len))
(struct eertree (nodes
rto ; odd length root node, or node -1 rte ; even length root node, or node 0 S ; accumulated input string, T=S[1..i] max-suf-t) ; maximum suffix of tree T #:mutable)
(define (new-eertree)
(let* ((rto (new-node #f -1)) (rte (new-node rto 0))) (eertree null rto rte (list 0) rte)))
(define (eertree-get-max-suffix-pal et start-node a)
#| We traverse the suffix-palindromes of T in the order of decreasing length. For each palindrome we read its length k and compare T[i-k] against a until we get an equality or arrive at the -1 node. |# (match et [(eertree nodes rto rte (and S (app length i)) max-suf-t) (let loop ((u start-node)) (let ((k (node-len u))) (if (or (eq? u rto) (= (list-ref S (- i k 1)) a)) u (let ((u→ (node-link u))) (when (eq? u u→) (error 'eertree-get-max-suffix-pal "infinite loop")) (loop u→)))))]))
(define (eertree-add! et a)
#| We need to find the maximum suffix-palindrome P of Ta Start by finding maximum suffix-palindrome Q of T. To do this, we traverse the suffix-palindromes of T in the order of decreasing length, starting with maxSuf(T) |# (match (eertree-get-max-suffix-pal et (eertree-max-suf-t et) a) [(node Q.edges Q.→ Q.len) ;; We check Q to see whether it has an outgoing edge labeled by a. (define new-node? (not (hash-has-key? Q.edges a))) (when new-node? (define P (new-node #f (+ Q.len 2))) ; We create the node P of length Q+2 (set-eertree-nodes! et (append (eertree-nodes et) (list P))) (define P→ (if (= (node-len P) 1) (eertree-rte et) ; if P = a, create the suffix link (P,0) ;; It remains to c reate the suffix link from P if |P|>1. ;; Just continue traversing suffix-palindromes of T starting with the suffix link of Q. (hash-ref (node-edges (eertree-get-max-suffix-pal et Q.→ a)) a))) (set-node-link! P P→) (hash-set! Q.edges a P)) ; create the edge (Q,P) (set-eertree-max-suf-t! et (hash-ref Q.edges a)) ; P becomes the new maxSufT (set-eertree-S! et (append (eertree-S et) (list a))) ; Store accumulated input string new-node?]))
(define (eertree-get-sub-palindromes et)
(define (inr nd (node-path (list nd)) (char-path/rev null)) ;; Each node represents a palindrome, which can be reconstructed by the path from the root node to ;; each non-root node. (let ((deeper ; Traverse all edges, since they represent other palindromes (for/fold ((result null)) (([→-name nd2] (in-hash (node-edges nd)))) ; The lnk-name is the character used for this edge (append result (inr nd2 (append node-path (list nd2)) (cons →-name char-path/rev))))) (root-node? (or (eq? (eertree-rto et) nd) (eq? (eertree-rte et) nd)))) (if root-node? ; Don't add root nodes deeper (let ((even-string? (eq? (car node-path) (eertree-rte et))) (char-path (reverse char-path/rev))) (cons (append char-path/rev (if even-string? char-path (cdr char-path))) deeper))))) inr)
(define (eertree-get-palindromes et)
(define sub (eertree-get-sub-palindromes et)) (append (sub (eertree-rto et)) (sub (eertree-rte et))))
(module+ main
(define et (new-eertree)) ;; eertree works in integer space, so we'll map to/from char space here (for ((c "eertree")) (eertree-add! et (char->integer c))) (map (compose list->string (curry map integer->char)) (eertree-get-palindromes et)))
</lang>
- Output:
'("t" "rtr" "ertre" "eertree" "r" "e" "ee")
Raku
(formerly Perl 6)
<lang perl6>my $str = "eertree"; my @pal = (); my ($strrev,$strpal);
for (1 .. $str.chars) -> $n {
for (1 .. $str.chars) -> $m { $strrev = ""; $strpal = $str.substr($n-1, $m); if ($strpal ne "") { for ($strpal.chars ... 1) -> $p { $strrev ~= $strpal.substr($p-1,1); } ($strpal eq $strrev) and @pal.push($strpal); } }
}
say @pal.unique; </lang>
- Output:
(e ee eertree ertre r rtr t)
REXX
This REXX program is modeled after the Ring example. <lang rexx>/*REXX program creates a list of (unique) sub─palindromes that exist in an input string.*/ parse arg x . /*obtain optional input string from CL.*/ if x== | x=="," then x= 'eertree' /*Not specified? Then use the default.*/ L= length(x) /*the length (in chars) of input string*/ @.= . /*@ tree indicates uniqueness of pals. */ $= /*list of unsorted & unique palindromes*/
do j=1 for L /*start at the left side of the string.*/ do k=1 for L /*traverse from left to right of string*/ parse var x =(j) y +(k) /*extract a substring from the string. */ if reverse(y)\==y | @.y\==. then iterate /*Partial string a palindrome? Skip it*/ @.y= y /*indicate a sub─palindrome was found. */ $= $' ' y /*append the sub─palindrome to the list*/ end /*k*/ /* [↑] an extra blank is inserted. */ end /*j*/
say '──────── The input string that is being used: ' space(x) say '──────── The number of sub─palindromes found: ' words($) say '──────── The list of sub─palindromes found: ' strip($)
/*stick a fork in it, we're all done. */</lang>
- output when using the default input:
──────── The input string that is being used: eertree ──────── The number of sub─palindromes found: 7 ──────── The list of sub─palindromes found: e ee eertree ertre r rtr t
Ring
<lang ring>
- Project : Eertree
str = "eertree" pal = [] for n=1 to len(str)
for m=1 to len(str) strrev = "" strpal = substr(str, n, m) if strpal != "" for p=len(strpal) to 1 step -1 strrev = strrev + strpal[p] next if strpal = strrev add(pal, strpal) ok ok next
next sortpal = sort(pal) for n=len(sortpal) to 2 step -1
if sortpal[n] = sortpal[n-1] del(sortpal, n) ok
next see sortpal + nl </lang> Output:
e ee eertree ertre r rtr t
Ruby
<lang ruby>class Node
def initialize(length, edges = {}, suffix = 0) @length = length @edges = edges @suffix = suffix end
attr_reader :length attr_reader :edges attr_accessor :suffix
end
EVEN_ROOT = 0 ODD_ROOT = 1
def eertree(s)
tree = [ Node.new(0, {}, ODD_ROOT), Node.new(-1, {}, ODD_ROOT) ] suffix = ODD_ROOT s.each_char.with_index { |c, i| n = suffix k = 0 loop do k = tree[n].length b = i - k - 1 if b >= 0 and s[b] == c then break end n = tree[n].suffix end if tree[n].edges.key?(c) then suffix = tree[n].edges[c] next end suffix = tree.length tree << Node.new(k + 2) tree[n].edges[c] = suffix if tree[suffix].length == 1 then tree[suffix].suffix = 0 next end loop do n = tree[n].suffix b = i - tree[n].length - 1 if b >= 0 and s[b] == c then break end end tree[suffix].suffix = tree[n].edges[c] } return tree
end
def subPalindromes(tree)
s = []
children = lambda { |n,p,f| for c,v in tree[n].edges m = tree[n].edges[c] p = c + p + c s << p f.call(m, p, f) end }
children.call(0, , children)
for c,n in tree[1].edges s << c children.call(n, c, children) end
return s
end
tree = eertree("eertree") print subPalindromes(tree), "\n"</lang>
- Output:
["ee", "e", "r", "t", "rtr", "ertre", "eertree"]
Visual Basic .NET
<lang vbnet>Module Module1
Class Node Public Sub New(Len As Integer) Length = Len Edges = New Dictionary(Of Char, Integer) End Sub
Public Sub New(len As Integer, edg As Dictionary(Of Char, Integer), suf As Integer) Length = len Edges = If(IsNothing(edg), New Dictionary(Of Char, Integer), edg) Suffix = suf End Sub
Property Edges As Dictionary(Of Char, Integer) Property Length As Integer Property Suffix As Integer End Class
ReadOnly EVEN_ROOT As Integer = 0 ReadOnly ODD_ROOT As Integer = 1
Function Eertree(s As String) As List(Of Node) Dim tree As New List(Of Node) From { New Node(0, New Dictionary(Of Char, Integer), ODD_ROOT), New Node(-1, New Dictionary(Of Char, Integer), ODD_ROOT) } Dim suffix = ODD_ROOT Dim n As Integer Dim k As Integer
For i = 1 To s.Length Dim c = s(i - 1) n = suffix While True k = tree(n).Length Dim b = i - k - 2 If b >= 0 AndAlso s(b) = c Then Exit While End If n = tree(n).Suffix End While If tree(n).Edges.ContainsKey(c) Then suffix = tree(n).Edges(c) Continue For End If suffix = tree.Count tree.Add(New Node(k + 2)) tree(n).Edges(c) = suffix If tree(suffix).Length = 1 Then tree(suffix).Suffix = 0 Continue For End If While True n = tree(n).Suffix Dim b = i - tree(n).Length - 2 If b >= 0 AndAlso s(b) = c Then Exit While End If End While Dim a = tree(n) Dim d = a.Edges(c) Dim e = tree(suffix) e.Suffix = d Next
Return tree End Function
Function SubPalindromes(tree As List(Of Node)) As List(Of String) Dim s As New List(Of String) Dim children As Action(Of Integer, String) = Sub(n As Integer, p As String) For Each c In tree(n).Edges.Keys Dim m = tree(n).Edges(c) Dim p1 = c + p + c s.Add(p1) children(m, p1) Next End Sub children(0, "") For Each c In tree(1).Edges.Keys Dim m = tree(1).Edges(c) Dim ct = c.ToString() s.Add(ct) children(m, ct) Next Return s End Function
Sub Main() Dim tree = Eertree("eertree") Dim result = SubPalindromes(tree) Dim listStr = String.Join(", ", result) Console.WriteLine("[{0}]", listStr) End Sub
End Module</lang>
- Output:
[ee, e, r, t, rtr, ertre, eertree]
Wren
<lang ecmascript>class Node {
construct new() { _edges = {} // edges (or forward links) _link = null // suffix link (backward links) _len = 0 // the length of the node }
edges { _edges } link { _link } link=(l) { _link = l } len { _len } len=(l) { _len = l }
}
class Eertree {
construct new(str) { _nodes = [] _rto = Node.new() // odd length root node, or node -1 _rte = Node.new() // even length root node, or node 0 _s = "0" // accumulated input string, T = S[1..i] _maxSufT = _rte // maximum suffix of tree T
// Initialize and build the tree _rte.link = _rto _rto.link = _rte _rto.len = -1 _rte.len = 0 for (ch in str) add_(ch) }
nodes { _nodes }
getMaxSuffixPal_(startNode, a) { // We traverse the suffix-palindromes of T in the order of decreasing length. // For each palindrome we read its length k and compare T[i-k] against a // until we get an equality or arrive at the -1 node. var u = startNode var i = _s.count var k = u.len while (u != _rto && _s[i - k - 1] != a) { if (u == u.link) Fiber.abort("Infinite loop detected") u = u.link k = u.len } return u }
add_(a) { // We need to find the maximum suffix-palindrome P of Ta // Start by finding maximum suffix-palindrome Q of T. // To do this, we traverse the suffix-palindromes of T // in the order of decreasing length, starting with maxSuf(T) var q = getMaxSuffixPal_(_maxSufT, a) // We check Q to see whether it has an outgoing edge labeled by a. var createANewNode = !q.edges.keys.contains(a)
if (createANewNode) { // We create the node P of length Q + 2 var p = Node.new() _nodes.add(p) p.len = q.len + 2 if (p.len == 1) { // if P = a, create the suffix link (P, 0) p.link = _rte } else { // It remains to create the suffix link from P if |P|>1. Just // continue traversing suffix-palindromes of T starting with the // the suffix link of Q. p.link = getMaxSuffixPal_(q.link, a).edges[a] }
// create the edge (Q, P) q.edges[a] = p }
// P becomes the new maxSufT _maxSufT = q.edges[a]
// Store accumulated input string _s = _s + a
return createANewNode }
getSubPalindromes() { // Traverse tree to find sub-palindromes var result = [] // Odd length words getSubPalindromes_(_rto, [_rto], "", result) // Even length words getSubPalindromes_(_rte, [_rte], "", result) return result }
getSubPalindromes_(nd, nodesToHere, charsToHere, result) { // Each node represents a palindrome, which can be reconstructed // by the path from the root node to each non-root node.
// Traverse all edges, since they represent other palindromes for (lnkName in nd.edges.keys) { var nd2 = nd.edges[lnkName] getSubPalindromes_(nd2, nodesToHere + [nd2], charsToHere + lnkName, result) }
// Reconstruct based on charsToHere characters. if (nd != _rto && nd != _rte) { // Don't print for root nodes var assembled = charsToHere[-1..0] + ((nodesToHere[0] == _rte) ? charsToHere : charsToHere[1..-1]) result.add(assembled) } }
}
var str = "eertree" System.print("Processing string '%(str)'") var eertree = Eertree.new(str) System.print("Number of sub-palindromes: %(eertree.nodes.count)") var result = eertree.getSubPalindromes() System.print("Sub-palindromes: %(result)")</lang>
- Output:
Processing string 'eertree' Number of sub-palindromes: 7 Sub-palindromes: [e, eertree, ertre, rtr, t, r, ee]
zkl
<lang zkl>class Node{
fcn init(length){ var edges=Dictionary(), # edges (or forward links). (char:Node) link=Void, # suffix link (backward links)
sz =length; # node length.
}
} class Eertree{
fcn init(string=Void){ var nodes=List(),
# two initial root nodes rto=Node(-1), # odd length root node, or node -1 rte=Node(0); # even length root node, or node 0
rto.link=rte.link=rto; # Initialize empty tree var S =Data(Void,0), # accumulated input string, T=S[1..i], byte buffer maxSufT=rte; # maximum suffix of tree T if(string) string.pump(addChar); // go ahead and build the tree } fcn get_max_suffix_pal(startNode,a){ # We traverse the suffix-palindromes of T in the order of decreasing length. # For each palindrome we read its length k and compare T[i-k] against a # until we get an equality or arrive at the -1 node. u,i,k := startNode, S.len(), u.sz; while(u.id!=rto.id and S.charAt(i - k - 1)!=a){
_assert_(u.id!=u.link.id); # Prevent infinte loop u,k = u.link,u.sz;
} return(u); } fcn addChar(a){
# We need to find the maximum suffix-palindrome P of Ta # Start by finding maximum suffix-palindrome Q of T. # To do this, we traverse the suffix-palindromes of T # in the order of decreasing length, starting with maxSuf(T)
Q:=get_max_suffix_pal(maxSufT,a); # We check Q to see whether it has an outgoing edge labeled by a. createANewNode:=(not Q.edges.holds(a)); if(createANewNode){
P:=Node(Q.sz + 2); nodes.append(P); if(P.sz==1) P.link=rte; # if P = a, create the suffix link (P,0) else # It remains to create the suffix link from P if |P|>1. Just # continue traversing suffix-palindromes of T starting with the suffix # link of Q. P.link=get_max_suffix_pal(Q.link,a).edges[a]; Q.edges[a]=P; # create the edge (Q,P)
} maxSufT=Q.edges[a]; # P becomes the new maxSufT S.append(a); # Store accumulated input string return(createANewNode); // in case anyone wants to know a is new edge } fcn get_sub_palindromes{ result:=List(); sub_palindromes(rto, T(rto),"", result); # Odd length words sub_palindromes(rte, T(rte),"", result); # Even length words result } fcn [private] sub_palindromes(nd, nodesToHere, charsToHere, result){ // nodesToHere needs to be read only
# Each node represents a palindrome, which can be reconstructed # by the path from the root node to each non-root node.
# Traverse all edges, since they represent other palindromes
nd.edges.pump(Void,'wrap([(lnkName,nd2)]){
sub_palindromes(nd2, nodesToHere+nd2, charsToHere+lnkName, result);
});
# Reconstruct based on charsToHere characters. if(nd.id!=rto.id and nd.id!=rte.id){ # Don't print for root nodes
if(nodesToHere[0].id==rte.id) # Even string assembled:=charsToHere.reverse() + charsToHere; else assembled:=charsToHere.reverse() + charsToHere[1,*]; # Odd string result.append(assembled);
} }
}</lang> <lang zkl>st:="eertree"; println("Processing string \"", st,"\""); eertree:=Eertree(st); println("Number of sub-palindromes: ", eertree.nodes.len()); println("Sub-palindromes: ", eertree.get_sub_palindromes());</lang>
- Output:
Processing string "eertree" Number of sub-palindromes: 7 Sub-palindromes: L("e","r","eertree","ertre","rtr","t","ee")