Eertree: Difference between revisions
m
→{{header|11l}}: Void
m (→{{header|Phix}}: added syntax colouring, made p2js compatible) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (7 intermediate revisions by 5 users not shown) | |||
Line 17:
* 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>
Line 22 ⟶ 23:
{{trans|D}}
<
Int length
Int suffix
Line 72 ⟶ 73:
[String] s
F children(Int n, String =p) ->
L(c, n) @tree[n].edges
p = c‘’p‘’c
Line 86 ⟶ 87:
V tree = eertree(‘eertree’)
print(subPalindromes(tree))</
{{out}}
Line 95 ⟶ 96:
=={{header|C sharp|C#}}==
{{trans|Java}}
<
using System.Collections.Generic;
Line 190 ⟶ 191:
}
}
}</
{{out}}
<pre>[ee, e, r, t, rtr, ertre, eertree]</pre>
Line 196 ⟶ 197:
=={{header|C++}}==
{{trans|D}}
<
#include <functional>
#include <map>
Line 316 ⟶ 317:
return 0;
}</
{{out}}
<pre>[ee, e, r, t, rtr, ertre, eertree]</pre>
Line 322 ⟶ 323:
=={{header|D}}==
{{trans|Go}}
<
import std.stdio;
Line 393 ⟶ 394:
}
return s.data;
}</
{{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}}==
<
import "fmt"
Line 471 ⟶ 518:
}
return
}</
{{out}}
<pre>
Line 479 ⟶ 526:
=={{header|Java}}==
{{trans|D}}
<
import java.util.HashMap;
import java.util.List;
Line 569 ⟶ 616:
}
}
}</
{{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}}
<
edges::Dict{Char, Node}
link::Union{Node, Missing}
Line 653 ⟶ 818:
eertree("eertree")
</
Results of processing string "eertree":
Number of sub-palindromes: 7
Line 661 ⟶ 826:
=={{header|Kotlin}}==
{{trans|Python}}
<
class Node {
Line 779 ⟶ 944:
val result = eertree.getSubPalindromes()
println("Sub-palindromes: $result")
}</
{{out}}
Line 789 ⟶ 954:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
If Version<9.5 Then exit
If Version=9.5 And Revision<2 Then Exit
Line 866 ⟶ 1,031:
Print Palindromes$(eertree("eertree"))
</syntaxhighlight>
{{out}}
<pre>
Line 874 ⟶ 1,039:
=={{header|Nim}}==
{{trans|Kotlin}}
<
type
Line 987 ⟶ 1,152:
echo fmt"Number of sub-palindromes: {eertree.nodes.len}"
let result = eertree.getSubPalindromes()
echo fmt"Sub-palindromes: {result.join("", "")}"</
{{out}}
Line 996 ⟶ 1,161:
=={{header|Objeck}}==
{{trans|Java}}
<
class Eertree {
Line 1,127 ⟶ 1,292:
return @edges;
}
}</
{{output}}
Line 1,136 ⟶ 1,301:
=={{header|Perl}}==
{{trans|Raku}}
<
for $n (1 .. length($str)) {
Line 1,151 ⟶ 1,316:
}
print join ' ', grep {not $seen{$_}++} @pal, "\n";</
{{out}}
<pre>e ee eertree ertre r rtr t</pre>
Line 1,157 ⟶ 1,322:
=={{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}.
<!--<
<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>
Line 1,237 ⟶ 1,402:
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</
{{out}}
The tree matches Fig 1 in the pdf linked above.
Line 1,257 ⟶ 1,422:
=={{header|Python}}==
<
from __future__ import print_function
Line 1,361 ⟶ 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 1,371 ⟶ 1,536:
{{trans|Python}}
<
(struct node (edges ; edges (or forward links)
link ; suffix link (backward links)
Line 1,456 ⟶ 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}}
Line 1,464 ⟶ 1,629:
(formerly Perl 6)
{{trans|Ring}}
<syntaxhighlight lang="raku"
my @pal = ();
my ($strrev,$strpal);
Line 1,482 ⟶ 1,647:
say @pal.unique;
</syntaxhighlight>
{{out}}
<pre>
Line 1,490 ⟶ 1,655:
=={{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.*/
Line 1,508 ⟶ 1,673:
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. */</
{{out|output|text= when using the default input:}}
<pre>
Line 1,517 ⟶ 1,682:
=={{header|Ring}}==
<
# Project : Eertree
Line 1,543 ⟶ 1,708:
next
see sortpal + nl
</syntaxhighlight>
Output:
<pre>
Line 1,557 ⟶ 1,722:
=={{header|Ruby}}==
{{trans|D}}
<
def initialize(length, edges = {}, suffix = 0)
@length = length
Line 1,635 ⟶ 1,800:
tree = eertree("eertree")
print subPalindromes(tree), "\n"</
{{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#}}
<
Class Node
Line 1,737 ⟶ 2,023:
End Sub
End Module</
{{out}}
<pre>[ee, e, r, t, rtr, ertre, eertree]</pre>
Line 1,743 ⟶ 2,029:
=={{header|Wren}}==
{{trans|Kotlin}}
<
construct new() {
_edges = {} // edges (or forward links)
Line 1,861 ⟶ 2,147:
System.print("Number of sub-palindromes: %(eertree.nodes.count)")
var result = eertree.getSubPalindromes()
System.print("Sub-palindromes: %(result)")</
{{out}}
Line 1,872 ⟶ 2,158:
=={{header|zkl}}==
{{trans|Python}}
<
fcn init(length){
var edges=Dictionary(), # edges (or forward links). (char:Node)
Line 1,947 ⟶ 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>
| |||