Eertree: Difference between revisions
→{{header|Phix}}
(promoted to (full) task status.) |
|||
Line 399:
Number of sub-palindromes: 7
Sub-palindromes: [e, r, eertree, ertre, rtr, t, ee]
</pre>
=={{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}.
<lang Phix>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] &= 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 = tree[i]
ti[NEXT] = sprint(ti[NEXT])
printf(1,"[%d]: len:%2d suffix:%d chars:%-5s next:%s\n",i&ti)
end for
puts(1,"\n")
-- odd then even lengths:
?children(children(s,tree,1), tree, 2)
end procedure
main()</lang>
{{out}}
The tree matches Fig 1 in the pdf linked above.
<pre>
tree:
[1]: len:-1 suffix:1 chars:ert next:{3,5,6}
[2]: len: 0 suffix:1 chars:e next:{4}
[3]: len: 1 suffix:2 chars: next:{}
[4]: len: 2 suffix:3 chars: next:{}
[5]: len: 1 suffix:2 chars: next:{}
[6]: len: 1 suffix:2 chars:r next:{7}
[7]: len: 3 suffix:5 chars:e next:{8}
[8]: len: 5 suffix:3 chars:e next:{9}
[9]: len: 7 suffix:4 chars: next:{}
{"e","r","t","rtr","ertre","eertree","ee"}
</pre>
| |||