119 lines
3.8 KiB
Text
119 lines
3.8 KiB
Text
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)")
|