title: Longest Common Substring: recursive solution?
body: <p>The common substring algorithm :</p>
  
  <pre><code>LCS(x,y) = 1+ LCS(x[0...xi-1],y[0...yj-1] if x[xi]==y[yj]
             else 0
  </code></pre>
  
  <p>Now the Dynamic Programming solution is well understood. However I am unable to figure out the recursive solution. If there are more than one substrings then the above algorithm seems to fail.</p>
  
  <p>Eg:</p>
  
  <pre><code>x = "LABFQDB" and y = "LABDB"
  </code></pre>
  
  <p>Applying the above algo</p>
  
  <pre><code>1+ (x=  "LABFQD" and y = "LABD")
  1+ (x=  "LABFQ" and y = "LAB")
  return 0 since 'Q'!='B'
  </code></pre>
  
  <p>The value returned would be 2 where i should have been 3?</p>
  
  <p>Can someone specify a recursive solution?</p>