Suffix tree: Difference between revisions
Added 11l
m (→{{header|Python}}: Remove use of mutable list as argument default (otherwise all "empty" nodes share the same children list which may be mutated by the algorithm)) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 19:
The computation time for an efficient algorithm should be <math>O(n)</math>, but such an algorithm might be difficult to implement. An easier, <math>O(n^2)</math> algorithm is accepted.
=={{header|11l}}==
{{trans|Python}}
<lang 11l>T Node
String sub
[Int] ch
F (sub, children)
.sub = sub
.ch = children
T SuffixTree
nodes = [Node(‘’, [Int]())]
F (str)
L(i) 0 .< str.len
.addSuffix(str[i..])
F addSuffix(suf)
V n = 0
V i = 0
L i < suf.len
V b = suf[i]
V x2 = 0
Int n2
L
V children = .nodes[n].ch
I x2 == children.len
n2 = .nodes.len
.nodes.append(Node(suf[i..], [Int]()))
.nodes[n].ch.append(n2)
R
n2 = children[x2]
I .nodes[n2].sub[0] == b
L.break
x2 = x2 + 1
V sub2 = .nodes[n2].sub
V j = 0
L j < sub2.len
I suf[i + j] != sub2[j]
V n3 = n2
n2 = .nodes.len
.nodes.append(Node(sub2[0 .< j], [n3]))
.nodes[n3].sub = sub2[j..]
.nodes[n].ch[x2] = n2
L.break
j = j + 1
i = i + j
n = n2
F visualize()
I .nodes.empty
print(‘<empty>’)
R
F f(Int n, String pre) -> N
V children = @.nodes[n].ch
I children.empty
print(‘-- ’(@.nodes[n].sub))
R
print(‘+- ’(@.nodes[n].sub))
L(c) children[0 .< (len)-1]
print(pre‘ +-’, end' ‘ ’)
@f(c, pre‘ | ’)
print(pre‘ +-’, end' ‘ ’)
@f(children.last, pre‘ ’)
f(0, ‘’)
SuffixTree(‘banana$’).visualize()</lang>
{{out}}
<pre>
+-
+- -- banana$
+- +- a
| +- +- na
| | +- -- na$
| | +- -- $
| +- -- $
+- +- na
| +- -- na$
| +- -- $
+- -- $
</pre>
=={{header|C sharp|C#}}==
| |||