Analysis

• Key: finding the extended locus

  • Otherwise, O(1) time

• Brute-force search: start from root and trace edges

  • Worst-case: AAAAAAA$.
  • |headi|=n-i for 1< i < n, n-i comparisons for each search
  • T (n2)

• Apostolico and Szpanowski (1992): average case: O(n log n)

  • Average maximum length of the longest common prefix of two suffixes is O(log n)
  • Probabilistic analysis

• McCreight – suffix links improve performance

Previous slide

Next slide

Back to first slide

View graphic version