Ukkonen’s suffix tree construction: Difference between revisions

 

As the task doesn't say whether overlapping sequences are to be counted, I've assumed that they are as this is what the algorithm naturally produces.

 

import (

fmt.Printf(" (this took %s)\n\n", elapsed)

}

 

{{out}}

{{trans|Go}}

Uses array indices instead of the Go version's node pointers.

 

"""The suffix-tree's node."""

 

testsuffixtree()

<pre>

Longest Repeated Substring in:

=={{header|Phix}}==

{{trans|Go}}

<span style="color: #000080;font-style:italic;">-- demo/rosetta/Ukkonens_Suffix_Tree.exw</span>

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" first %,d d.p. of Pi is: %s (%s)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

 

Having done that, the timings for extracting the longest repeated sequence of digits are reasonably quick and fairly linear as expected.

import "/dynamic" for Struct

import "/trait" for ByRef

var elapsed = (System.clock - start) * 1000

System.print(" (this took %(elapsed) ms)\n")

 

{{out}}