title: How do Suffix Trees work?
body: <p>I'm going through the data structures chapter in <a href="https://rads.stackoverflow.com/amzn/click/com/0387948600" rel="noreferrer" rel="nofollow noreferrer">The Algorithm Design Manual</a> and came across Suffix Trees. </p>
  
  <p>The example states:</p>
  
  <p>Input:</p>
  
  <pre><code>XYZXYZ$
   YZXYZ$
    ZXYZ$
     XYZ$
      YZ$
       Z$
        $
  </code></pre>
  
  <p>Output:</p>
  
  <p><img src="https://i.stack.imgur.com/UUgIX.png" alt="enter image description here"></p>
  
  <p>I'm not able to understand how that tree gets generated from the given input string. Suffix trees are used to find a given Substring in a given String, but how does the given tree help towards that? I do understand another given example of a trie shown below, but if the below trie gets compacted to a suffix tree, then what would it look like?</p>
  
  <p><img src="https://i.stack.imgur.com/12LO6.png" alt="enter image description here"></p>