76 lines
2.3 KiB
Text
76 lines
2.3 KiB
Text
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 :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$,)
|
|
\\ better use lambda() and not children()
|
|
\\ for recursion when we copy this lambda to other identifier.
|
|
s = lambda(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"))
|