Eertree: Difference between revisions
m
→{{header|11l}}: Void
Thundergnat (talk | contribs) m (Convert reference links to wikipedia links (which actually contain some useful information on the subject.)) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (44 intermediate revisions by 17 users not shown) | |||
Line 1:
[[Category:String algorithms]]
[[Category:Palindromes]]
{{
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
See links below.
Line 13 ⟶ 14:
;See also:
* Wikipedia entry: [https://en.wikipedia.org/wiki/Trie trie].
* Wikipedia entry: [https://en.wikipedia.org/wiki/Suffix_tree suffix tree]
* [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].
*EERTREE: An efficient data structure for processing palindromes in strings[https://www.sciencedirect.com/science/article/pii/S0195669817301294]
<br><br>
=={{header|11l}}==
{{trans|D}}
<syntaxhighlight 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
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) -> Void
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))</syntaxhighlight>
{{out}}
<pre>
[ee, e, r, t, rtr, ertre, eertree]
</pre>
=={{header|C sharp|C#}}==
{{trans|Java}}
<syntaxhighlight 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);
}
}
}</syntaxhighlight>
{{out}}
<pre>[ee, e, r, t, rtr, ertre, eertree]</pre>
=={{header|C++}}==
{{trans|D}}
<syntaxhighlight 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;
}</syntaxhighlight>
{{out}}
<pre>[ee, e, r, t, rtr, ertre, eertree]</pre>
=={{header|D}}==
{{trans|Go}}
<syntaxhighlight 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;
}</syntaxhighlight>
{{out}}
<pre>["ee", "e", "r", "t", "rtr", "ertre", "eertree"]</pre>
=={{header|FreeBASIC}}==
{{trans|Ring}}
<syntaxhighlight lang="vbnet">Dim As String cadena = "eertree"
Dim As Integer n, m, p, cnt = 0
Dim As String strpal, strrev
Dim As String pal(1 To Len(cadena)^2)
For n = 1 To Len(cadena)
For m = n To Len(cadena)
strpal = Mid(cadena, n, m-n+1)
strrev = ""
For p = Len(strpal) To 1 Step -1
strrev &= Mid(strpal, p, 1)
Next p
If strpal = strrev Then
cnt += 1
pal(cnt) = strpal
End If
Next m
Next n
For n = 1 To cnt-1
For m = n+1 To cnt
If pal(n) > pal(m) Then
Swap pal(n), pal(m)
End If
Next m
Next n
For n = cnt To 2 Step -1
If pal(n) = pal(n-1) Then
For m = n To cnt-1
pal(m) = pal(m+1)
Next m
cnt -= 1
End If
Next n
For n = 1 To cnt
Print pal(n)
Next n
Sleep</syntaxhighlight>
{{out}}
<pre>Same as Ring entry.</pre>
=={{header|Go}}==
<syntaxhighlight 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
}</syntaxhighlight>
{{out}}
<pre>
[ee e r t rtr ertre eertree]
</pre>
=={{header|Java}}==
{{trans|D}}
<syntaxhighlight 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);
}
}
}</syntaxhighlight>
{{out}}
<pre>[ee, r, t, rtr, ertre, eertree, e]</pre>
=={{header|JavaScript}}==
{{trans|Python}}
<syntaxhighlight lang="julia">
class Node {
constructor(len, suffix, id, level) {
this.edges = new Map(); // edges <Character, Node>
this.link = suffix; // Suffix link points to another node
this.length = len; // Length of the palindrome represented by this node
this.palindrome = "";
this.parent = null;
}
}
class Eertree {
constructor() {
this.imaginary = new Node(-1, null, this.count++, 1); // also called odd length root node
this.empty = new Node(0, this.imaginary, this.count++, 2); // also called even length root node
this.maxSuffixOfT = this.empty; // this is the current node we are on also the maximum Suffix of tree T
this.s = ""; // String processed by the Eertree
}
/**
* Add will only add at most 1 node to the tree.
* We get the max suffix palindrome with the same character before it
* so we can get cQc which will be the new palindrome, c otherwise
* If the node is already in the tree then we return 0 and create no new nodes
* @param {Character} c
* @returns int 1 if it created a new node an 0 otherwise
*/
add(c){
/**
* Traverse the suffix palindromes of T in the order of decreasing length
* Keep traversing until we get to imaginary node or until T[len - k] = a
* @param {Node} startNode
* @param {Character} a
* @returns {Node} u
*/
const getMaxSuffixPalindrome = (startNode, a) =>{
let u = startNode;
let n = this.s.length;
let k = u.length;
while(u !== this.imaginary && this.s[n - k - 1] !== a){
if(u === u.link){
throw new Error('Infinite Loop');
}
u = u.link;
k = u.length;
}
return u;
};
let Q = getMaxSuffixPalindrome(this.maxSuffixOfT, c);
let createNewNode = !(Q.edges.has(c));
if(createNewNode){
let P = new Node();
P.length = Q.length + 2;
// this is because Q is a palindrome and the suffix and prefix == c so cQc = P
//P.length == 1 if Q is the imaginary node
if(P.length === 1){
P.link = this.empty;
P.palindrome = c;
}
else{
/**
* Now we need to find the node to suffix link to
* Continue traversing suffix palindromes of T starting with the suffix
* we found earlier 's link
*/
P.link = getMaxSuffixPalindrome(Q.link, c).edges.get(c);
P.palindrome = c + Q.palindrome + c;
}
P.parent = Q;
Q.edges.set(c, P);
}
this.maxSuffixOfT = Q.edges.get(c);
this.s += c;
return createNewNode === true ? 1 : 0;
}
traverse(){
let subpalindromes = [];
const dfs = (node) => {
if(node !== this.imaginary && node !== this.empty){
subpalindromes.push(node.palindrome);
}
for(let [_, childNode] of node.edges){
dfs(childNode);
}
}
dfs(this.imaginary);
dfs(this.empty);
return subpalindromes;
}
}
var getSubpalindromes = function(s) {
let eertree = new Eertree();
for(let c of s){
eertree.add(c);
}
return eertree.traverse();
}
console.log(getSubpalindromes('eertree'));
</syntaxhighlight> {{output}} <pre>
Results of processing string "eertree":
Number of sub-palindromes: 7
Sub-palindromes: ["e", "r", "t", "rtr", "ertre", "eertree", "ee"]
</pre>
=={{header|Julia}}==
{{trans|Python}}
<syntaxhighlight 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")
</syntaxhighlight> {{output}} <pre>
Results of processing string "eertree":
Number of sub-palindromes: 7
Sub-palindromes: ["e", "r", "eertree", "ertre", "rtr", "t", "ee"]
</pre>
=={{header|Kotlin}}==
{{trans|Python}}
<
class Node {
Line 136 ⟶ 944:
val result = eertree.getSubPalindromes()
println("Sub-palindromes: $result")
}</
{{out}}
Line 143 ⟶ 951:
Number of sub-palindromes: 7
Sub-palindromes: [e, r, eertree, ertre, rtr, t, ee]
</pre>
=={{header|M2000 Interpreter}}==
<syntaxhighlight 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"))
</syntaxhighlight>
{{out}}
<pre>
("ee", "e", "r", "t", "rtr", "ertre", "eertree")
</pre>
=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight 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("", "")}"</syntaxhighlight>
{{out}}
<pre>Processing string: 'eertree'
Number of sub-palindromes: 7
Sub-palindromes: r, eertree, ertre, rtr, t, e, ee</pre>
=={{header|Objeck}}==
{{trans|Java}}
<syntaxhighlight 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;
}
}</syntaxhighlight>
{{output}}
<pre>
[ee, e, r, t, rtr, ertre, eertree]
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight 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";</syntaxhighlight>
{{out}}
<pre>e ee eertree ertre r rtr t</pre>
=={{header|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}.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">LEN</span><span style="color: #0000FF;">,</span><span style="color: #000000;">SUFF</span><span style="color: #0000FF;">,</span><span style="color: #000000;">CHARS</span><span style="color: #0000FF;">,</span><span style="color: #000000;">NEXT</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">suffix</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">chars</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">={})</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">len</span><span style="color: #0000FF;">,</span><span style="color: #000000;">suffix</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chars</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- must match above enum!</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">eertree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">node</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- odd lengths</span>
<span style="color: #000000;">node</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)}</span> <span style="color: #000080;font-style:italic;">-- even lengths</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">suff</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span> <span style="color: #000080;font-style:italic;">-- max suffix palindrome</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">cur</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">suff</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">curlen</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">k</span>
<span style="color: #008080;">while</span> <span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">curlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">LEN</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">curlen</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">ch</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">cur</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">SUFF</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHARS</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">suff</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">node</span><span style="color: #0000FF;">(</span><span style="color: #000000;">curlen</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">suff</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHARS</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">ch</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">])&</span><span style="color: #000000;">suff</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">suff</span><span style="color: #0000FF;">][</span><span style="color: #000000;">LEN</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">suff</span><span style="color: #0000FF;">][</span><span style="color: #000000;">SUFF</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">while</span> <span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">cur</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">SUFF</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">curlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">LEN</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">curlen</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">ch</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHARS</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">suff</span><span style="color: #0000FF;">][</span><span style="color: #000000;">SUFF</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cur</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">tree</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">children</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHARS</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHARS</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">nxt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #0000FF;">?</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">&</span><span style="color: #008000;">""</span>
<span style="color: #0000FF;">:</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">&</span><span style="color: #000000;">root</span><span style="color: #0000FF;">&</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">children</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nxt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tree</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">eertree</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"eertree"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"tree:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">ti</span><span style="color: #0000FF;">[</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">[</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">&</span><span style="color: #000000;">ti</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"[%d]: len:%2d suffix:%d chars:%-5s next:%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- odd then even lengths:</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">children</span><span style="color: #0000FF;">(</span><span style="color: #000000;">children</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
The tree matches Fig 1 in the pdf linked above.
<pre>
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"}
</pre>
=={{header|Python}}==
<
from __future__ import print_function
Line 251 ⟶ 1,526:
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)</
{{out}}
Line 261 ⟶ 1,536:
{{trans|Python}}
<
(struct node (edges ; edges (or forward links)
link ; suffix link (backward links)
Line 346 ⟶ 1,621:
(for ((c "eertree")) (eertree-add! et (char->integer c)))
(map (compose list->string (curry map integer->char)) (eertree-get-palindromes et)))
</syntaxhighlight>
{{out}}
<pre>'("t" "rtr" "ertre" "eertree" "r" "e" "ee")</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Ring}}
<syntaxhighlight lang="raku" line>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;
</syntaxhighlight>
{{out}}
<pre>
(e ee eertree ertre r rtr t)
</pre>
=={{header|REXX}}==
This REXX program is modeled after the '''Ring''' example.
<
parse arg x . /*obtain optional input string from CL.*/
if x=='' | x=="," then x= 'eertree' /*Not specified? Then use the default.*/
L= length(x)
@.=
$= /*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($)
{{out|output|text= when using the default input:}}
<pre>
────────
──────── The number of sub─palindromes found: 7
──────── The list of sub─palindromes found: e ee eertree ertre r rtr t
</pre>
=={{header|Ring}}==
<
# Project : Eertree
str = "eertree"
Line 423 ⟶ 1,708:
next
see sortpal + nl
</syntaxhighlight>
Output:
<pre>
Line 433 ⟶ 1,718:
rtr
t
</pre>
=={{header|Ruby}}==
{{trans|D}}
<syntaxhighlight 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"</syntaxhighlight>
{{out}}
<pre>["ee", "e", "r", "t", "rtr", "ertre", "eertree"]</pre>
=={{header|Rust}}==
{{trans|Go}}
<syntaxhighlight lang="Rust">
use std::collections::HashMap;
use std::convert::TryInto;
struct Node {
length: isize,
edges: HashMap<u8, usize>,
suffix: usize,
}
impl Node {
fn new(length: isize, suffix: usize) -> Self {
Node {
length,
suffix,
edges: HashMap::new(),
}
}
}
const EVEN_ROOT: usize = 0;
const ODD_ROOT: usize = 1;
fn eertree(s: &[u8]) -> Vec<Node> {
let mut tree = vec![
Node::new(0, ODD_ROOT), // even root
Node::new(-1, ODD_ROOT), // odd root
];
let mut suffix = ODD_ROOT;
for (i, &c) in s.iter().enumerate() {
let mut n = suffix;
let mut k;
loop {
k = tree[n].length;
let k_plus_one: usize = (k + 1).try_into().unwrap_or(0);
if let Some(b) = i.checked_sub(k_plus_one) {
if b < s.len() && s[b] == c {
break;
}
}
n = tree[n].suffix;
}
if tree[n].edges.contains_key(&c) {
suffix = tree[n].edges[&c];
continue;
}
suffix = tree.len();
tree.push(Node::new(k + 2, 0));
tree[n].edges.insert(c, suffix);
if tree[suffix].length == 1 {
tree[suffix].suffix = EVEN_ROOT;
continue;
}
loop {
n = tree[n].suffix;
let tree_n_length_plus_one: usize = (tree[n].length + 1).try_into().unwrap_or(0);
if let Some(b) = i.checked_sub(tree_n_length_plus_one) {
if b < s.len() && s[b] == c {
break;
}
}
}
tree[suffix].suffix = tree[n].edges[&c];
}
tree
}
fn sub_palindromes(tree: &[Node]) -> Vec<String> {
let mut result = Vec::new();
fn children(node: usize, p: String, tree: &[Node], result: &mut Vec<String>) {
for (&c, &n) in &tree[node].edges {
let c = c as char;
let p_new = format!("{}{}{}", c, p, c);
result.push(p_new.clone());
children(n, p_new, tree, result);
}
}
children(EVEN_ROOT, String::new(), tree, &mut result);
for (&c, &n) in &tree[ODD_ROOT].edges {
let c = c as char;
let p = c.to_string();
result.push(p.clone());
children(n, p, tree, &mut result);
}
result
}
fn main() {
let tree = eertree(b"eertree");
let palindromes = sub_palindromes(&tree);
for palindrome in palindromes {
println!("{}", palindrome);
}
}
</syntaxhighlight>
{{out}}
<pre>
ee
e
t
rtr
ertre
eertree
r
</pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>[ee, e, r, t, rtr, ertre, eertree]</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">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)")</syntaxhighlight>
{{out}}
<pre>
Processing string 'eertree'
Number of sub-palindromes: 7
Sub-palindromes: [e, eertree, ertre, rtr, t, r, ee]
</pre>
=={{header|zkl}}==
{{trans|Python}}
<
fcn init(length){
var edges=Dictionary(), # edges (or forward links). (char:Node)
Line 512 ⟶ 2,233:
}
}
}</
<
println("Processing string \"", st,"\"");
eertree:=Eertree(st);
println("Number of sub-palindromes: ", eertree.nodes.len());
println("Sub-palindromes: ", eertree.get_sub_palindromes());</
{{out}}
<pre>
| |||