title: printing Diff from Longest Common Subsequence
body: <p>So I've been doing some practice problems for both Perl &amp; Python (kinda choosing between the 2) and I got a problem where I need to make my own diff algorithm just like Github's. 
  I'm up to the point where I know that the Longest Common Subsequence problem is a big part of the solution. I used the <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem" rel="nofollow">wikipedia page for LCS</a> as reference but I'm still having trouble figuring out the diff part.</p>
  
  <p>I also realize there are already modules on CPAN like Algorithm:Diff, but this is mostly just for practice and those feel like cheating. </p>
  
  <p>I figured out the python/pseudocode version of the algorithm but I plan on doing it with multi-dimensional arrays, which Perl doesn't seem to have.</p>
  
  <p>Now I'm up to where I can successfully get the Longest Common Subsequence length in Perl.</p>
  
  <p>Basically the pseudocode (almost python-like, but is supposed to be for Perl) I can think of is something like this:</p>
  
  <pre><code>function lengthOfLCS(string1, string2){
      if length(string1) == 0 or length(string2) == 0:
           return 0
      else if string1[0] eq string2[0]: 
           return 1+ lengthOfLCS(stringA[1:], stringB[1:])
      return max(lengthOfLCS(string1, string2[1:], lengthOfLCS(string1[1:], string2))
  </code></pre>
  
  <p>I haven't implemented it yet, but I think that's basically how I can calculate the length of LCS of two strings?</p>
  
  <p>Output wise, it should return 4 against "HUMAN" &amp; "CHIMPANZEE" (LCS = HMAN)</p>
  
  <p>So what I'm asking is how do I get to printing Diffs using Perl from this point on? I'm aware that instead of only the length of the LCS, I should've a List/Array returned instead, which is doable by returning a multi-dimensional list in the LCS function and then processing it later on in a separate diff function.</p>
  
  <p>I'm kinda new to Perl, so any pointers/tips would be greatly appreciated.
  Thanks.</p>