Anonymous user
Eertree: Difference between revisions
no edit summary
No edit summary |
|||
Line 586:
Number of sub-palindromes: 7
Sub-palindromes: [e, r, eertree, ertre, rtr, t, ee]
</pre>
=={{header|M2000 Interpreter}}==
<lang M2000 Interpreter>
If Version<9.5 Then exit
If Version=9.5 And Revision<2 Then Exit
Class Node {
inventory myedges
length, suffix=0
Function edges(s$) {
=-1 : if exist(.myedges, s$) then =eval(.myedges)
}
Module edges_append (a$, where) {
Append .myedges, a$:=where
}
Class:
Module Node(.length) {
Read ? .suffix, .myedges
}
}
function eertree(s$) {
Const evenRoot=0, oddRoot=1
Inventory Tree= oddRoot:=Node(-1,1),evenRoot:=Node(0,1)
k=0
suffix=oddRoot
for i=0 to len(s$)-1 {
c$=mid$(s$,i+1,1)
n=suffix
Do {
k=tree(n).length
b=i-k-1
if b>=0 then if mid$(s$,b+1,1)=c$ Then exit
n =tree(n).suffix
} Always
e=tree(n).edges(c$)
if e>=0 then suffix=e : Print "find in :";n :continue
suffix=len(Tree)
Append Tree, len(Tree):=Node(k+2)
Tree(n).edges_append c$, suffix
If tree(suffix).length=1 then tree(suffix).suffix=0 : continue
Do {
n=tree(n).suffix
b=i-tree(n).length-1
if b>0 Then If mid$(s$, b+1,1)=c$ then exit
} Always
e=tree(n).edges(c$)
if e>=0 then tree(suffix).suffix=e
}
=tree
}
children=lambda (s, tree, n, root$="")->{
L=Len(tree(n).myEdges)
if L=0 then =s : exit
L--
For i=0 to L {
c=tree(n).myEdges
c$=Eval$(c, i) ' read keys at position i
nxt=c(i!) ' read value using position
p$ = if$(n=1 -> c$, c$+root$+c$)
append s, (p$,)
s = children(s, tree, nxt, p$)
}
= s
}
aString=Lambda ->{
Push Quote$(Letter$)
}
aLine=Lambda ->{
Shift 2 ' swap two top stack items
if stackitem$()="" then { Drop} Else Push letter$+", "+Letter$
}
Palindromes$=Lambda$ children, aString, aLine (Tree)-> {
="("+children(children((,), Tree, 0), Tree, 1)#Map(aString)#Fold$(aline,"")+")"
}
Print Palindromes$(eertree("eertree"))
</lang>
{{out}}
<pre>
("ee", "e", "r", "t", "rtr", "ertre", "eertree")
</pre>
| |||