Ukkonen’s Suffix Tree Construction
Suffix Trees are very useful in numerous string processing and computational biology problems.
The task is to create a function which implements Ukkonen’s algorithm to create a useful Suffix Tree as described:
Using Arithmetic-geometric mean/Calculate Pi generate the first 1000, 10000, and 100000 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.