Eertree: Difference between revisions
m
→{{header|11l}}: Void
imported>Patuitar |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (4 intermediate revisions by 3 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 72 ⟶ 73:
[String] s
F children(Int n, String =p) ->
L(c, n) @tree[n].edges
p = c‘’p‘’c
Line 396 ⟶ 397:
{{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}}==
Line 656 ⟶ 703:
}
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", "
</pre>
Line 1,729 ⟶ 1,803:
{{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}}==
| |||