Eertree: Difference between revisions
Go solution
Walterpachl (talk | contribs) m (tried to fix the links) |
(Go solution) |
||
Line 17:
* [https://arxiv.org/abs/1506.04862 Cornell University Library, Computer Science, Data Structures and Algorithms ───► EERTREE: An Efficient Data Structure for Processing Palindromes in Strings].
<br><br>
=={{header|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>
{{out}}
<pre>
[ee e r t rtr ertre eertree]
</pre>
=={{header|Kotlin}}==
| |||