title: calculating Lempel-Ziv (LZ) complexity (aka sequence complexity) of a binary string
body: <p>I need to calculate the LZ-complexity of a binary string. The LZ-complexity is the number of differencet substrings encountered as the stream is viewed from begining to the end. As an example:</p>
  
  <p>s = 1001111011000010</p>
  
  <p>Marking in the different substrings the sequence complexity c(s) = 6:
  s = 1 / 0 / 01 / 1110 / 1100 / 0010 /</p>
  
  <p>can someone guide me to find a simple solution for that? I am sure there should be some very straight-forward implementations for this well-known problem, but I have difficulty finding them. Can it be done simply done with constructing a suffix tree or something similar. If yes, exactly how? and what should I do? </p>
  
  <p>anyone knows of any c/c++ source code to accomplish the task?</p>
  
  <p>thanks in advance.</p>
  
  <p>to clarify the construction of the tree suggested in the answers. Does the tree looks like this?</p>
  
  <pre><code>         o
         /   \
        o     o
       / \   / \
      o   o o   o
         /     /
        o     o
  </code></pre>