Formalities & Definitions

• Y: Suffix tree for string y, |y|=n

  • n leaves
  • Storage O(n)
  • Left-Child, Right Sibling Structure

• Edges: substrings y(k,l)

• Internal Nodes: longest common prefix of string’s suffixes.

• Locus: node representing a string

• Extension: string with u as a prefix

• Extended Locus: Locus of shortest extension of u that is found in tree

• Contracted Locus: Locus of longest prefix of u in tree

• Headi : longest prefix of y(i,n) which is a prefix of y(j,n) for some j<I

• Taili : y(i,n)=headitaili

suf4 = BC

head4=BC

tail4 = $

Previous slide

Next slide

Back to first slide

View graphic version