Suffix Trie

  • Checks if a String is a Substring of another string
  • Search longest common prefix
  • k-ths prefix
  // Example for String abac
        *
       /|\
      / | \
     a  b  c
    /|  |
   / |  |
  b  c  a
  |     |
  |     |
  a     c
  |
  |
  c

Building tree is in $O(n^2)$. Faster implementation with suffix tree.

Easier algorithm: Suffix array