title: Ratcliff-Obershelp string similarity
body: <p>I need to implement the <strong>Ratcliff-Obershelp</strong> (aka Gestalt Pattern Matching) algorithm and I'm stuck at building the recursive part.</p>
  <p>I have built the lcs (longest common substring) intermediate function (using dynamic programming), now i need to apply it to the 2 compared strings.</p>
  <p>Example:</p>
  <pre><code>lcs(&quot;WIKIMEDIA&quot;, &quot;REMEDY&quot;) = &quot;MED&quot;
  </code></pre>
  <p>Taking both sides (left-right) of each string, the new string chunks to compare:</p>
  <pre><code>(&quot;WIKI&quot;, &quot;RE&quot;) and (&quot;IA&quot;, &quot;Y&quot;); 
  </code></pre>
  <p>both return lcs = 0, but i need to implement this in an recursive way, as the 2 initial strings may result in 4 chunks to &quot;lcs&quot;-compare, and then 8, etc.</p>
  <p>The exit condition would be either &quot;lcs = 0&quot; or &quot;one of the strings is empty&quot; (preferred over the former condition)
  Any pseudo code would help.
  Thanks!</p>