(phixonline)-->
with javascript_semantics
enum LEN,SUFF,CHARS,NEXT
function node(integer len, suffix=1, string chars="", sequence next={})
return {len,suffix,chars,next} -- must match above enum!
end function
function eertree(string s)
sequence tree = {node(-1), -- odd lengths
node(0)} -- even lengths
integer suff = 2 -- max suffix palindrome
for i=1 to length(s) do
integer cur = suff, curlen, ch = s[i], k
while (true) do
curlen = tree[cur][LEN]
k = i-1-curlen
if k>=1 and s[k]==ch then
exit
end if
cur = tree[cur][SUFF]
end while
k = find(ch,tree[cur][CHARS])
if k then
suff = tree[cur][NEXT][k]
else
tree = append(tree,node(curlen+2))
suff = length(tree)
tree[cur][CHARS] &= ch
tree[cur][NEXT] = deep_copy(tree[cur][NEXT])&suff
if tree[suff][LEN]==1 then
tree[suff][SUFF] = 2
else
while (true) do
cur = tree[cur][SUFF]
curlen = tree[cur][LEN]
k = i-1-curlen
if k>=0 and s[k]==ch then
k = find(ch,tree[cur][CHARS])
if k then
tree[suff][SUFF] = tree[cur][NEXT][k]
end if
exit
end if
end while
end if
end if
end for
return tree
end function
function children(sequence s, tree, integer n, string root="")
for i=1 to length(tree[n][CHARS]) do
integer c = tree[n][CHARS][i],
nxt = tree[n][NEXT][i]
string p = iff(n=1 ? c&""
: c&root&c)
s = append(s, p)
s = children(s, tree, nxt, p)
end for
return s
end function
procedure main()
sequence tree = eertree("eertree")
puts(1,"tree:\n")
for i=1 to length(tree) do
sequence ti = deep_copy(tree[i])
ti[NEXT] = sprint(ti[NEXT])
ti = i&ti
printf(1,"[%d]: len:%2d suffix:%d chars:%-5s next:%s\n",ti)
end for
puts(1,"\n")
-- odd then even lengths:
?children(children({},tree,1), tree, 2)
end procedure
main()