Ukkonen’s suffix tree construction
Suffix Trees are very useful in numerous string processing and computational biology problems.
Ukkonen’s suffix tree construction is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
The task is to create a function which implements Ukkonen’s algorithm to create a useful Suffix Tree as described:
Part 1 Part 2 Part 3 Part 4 Part 5 Part 6
Using Arithmetic-geometric mean/Calculate Pi generate the first 1000, 10000, and 1000000 decimal places of pi. Using your implementation with an alphabet of 0 through 9 (plus $ say to make the tree explicit) find the longest repeated string in each list. Time your results and demonstrate that your implementation is linear (i.e. that 10000 takes approx. 10 times as long as 1000). You may vary the size of the lists of decimal places of pi to give reasonable answers.