Eertree: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 586: | Line 586: | ||
Number of sub-palindromes: 7 |
Number of sub-palindromes: 7 |
||
Sub-palindromes: [e, r, eertree, ertre, rtr, t, ee] |
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> |
</pre> |
||