Ukkonen’s suffix tree construction: Difference between revisions

Using [[Arithmetic-geometric mean/Calculate Pi]] generate the first 1000, 10000, and 1000000100000 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.