title: Is this an acceptable algorithm?
body: <p>I've designed an algorithm to find the longest common subsequence. these are steps:  </p>
  
  <ul>
  <li><p>Pick the first letter in the first string.</p></li>
  <li><p>Look for it in the second string and if its found, Add that letter to
  <code>common_subsequence</code> and store its position in <code>index</code>, Otherwise
  compare the length of <code>common_subsequence</code> with the length of <code>lcs</code>
  and if its greater, asign its value to <code>lcs</code>.</p></li>
  <li><p>Return to the first string and pick the next letter and repeat the
  previous step again, But this time start searching from <code>index</code>th letter</p></li>
  <li><p>Repeat this process until there is no letter in the first string to
  pick. At the end the value of <code>lcs</code> is the Longest Common
  Subsequence.</p></li>
  </ul>
  
  <p>This is an example:<br>
  ‫‪</p>
  
  <pre><code>X=A, B, C, B, D, A, B‬‬  
  ‫‪Y=B, D, C, A, B, A‬‬ 
  </code></pre>
  
  <p>Pick <code>A</code> in the first string.<br>
  Look for <code>A</code> in <code>Y</code>.<br>
  Now that there is an <code>A</code> in the second string, append it to <code>common_subsequence</code>.<br>
  Return to the first string and pick the next letter that is <code>B</code>.
  Look for <code>B</code> in the second string this time starting from the position of <code>A</code>.<br>
  There is a <code>B</code> after <code>A</code> so append B to <code>common_subsequence</code>.<br>
  Now pick the next letter in the first string that is <code>C</code>. There isn't a <code>C</code> next to <code>B</code> in the second string. So assign the value of common_subsequence to <code>lcs</code> because its length is greater than the length of <code>lcs</code>.
  repeat the previous steps until reaching the end of the first string. In the end the value of <code>lcs</code> is the Longest Common Subsequence.</p>
  
  <p>The complexity of this algorithm is theta(n*m).
  Here is my implementations:  </p>
  
  <p>First algorithm:</p>
  
  <pre><code>import time
  def lcs(xstr, ystr):
      if not (xstr and ystr): return # if string is empty
      lcs = [''] #  longest common subsequence
      lcslen = 0 # length of longest common subsequence so far
      for i in xrange(len(xstr)):
          cs = '' # common subsequence
          start = 0 # start position in ystr
          for item in xstr[i:]:
              index = ystr.find(item, start) # position at the common letter
              if index != -1: # if common letter has found
                  cs += item # add common letter to the cs
                  start = index + 1
              if index == len(ystr) - 1: break # if reached end of the ystr
          # update lcs and lcslen if found better cs
          if len(cs) &gt; lcslen: lcs, lcslen = [cs], len(cs) 
          elif len(cs) == lcslen: lcs.append(cs)
      return lcs
  
  file1 = open('/home/saji/file1')
  file2 = open('/home/saji/file2')
  xstr = file1.read()
  ystr = file2.read()
  
  start = time.time()
  lcss = lcs(xstr, ystr)
  elapsed = (time.time() - start)
  print elapsed
  </code></pre>
  
  <p>The same algorithm using hash table:</p>
  
  <pre><code>import time
  from collections import defaultdict
  def lcs(xstr, ystr):
      if not (xstr and ystr): return # if strings are empty
      lcs = [''] #  longest common subsequence
      lcslen = 0 # length of longest common subsequence so far
      location = defaultdict(list) # keeps track of items in the ystr
      i = 0
      for k in ystr:
          location[k].append(i)
          i += 1
      for i in xrange(len(xstr)):
          cs = '' # common subsequence
          index = -1
          reached_index = defaultdict(int)
          for item in xstr[i:]:
              for new_index in location[item][reached_index[item]:]:
                  reached_index[item] += 1
                  if index &lt; new_index:
                      cs += item # add item to the cs
                      index = new_index
                      break
              if index == len(ystr) - 1: break # if reached end of the ystr
          # update lcs and lcslen if found better cs
          if len(cs) &gt; lcslen: lcs, lcslen = [cs], len(cs) 
          elif len(cs) == lcslen: lcs.append(cs)
      return lcs
  
  file1 = open('/home/saji/file1')
  file2 = open('/home/saji/file2')
  xstr = file1.read()
  ystr = file2.read()
  
  start = time.time()
  lcss = lcs(xstr, ystr)
  elapsed = (time.time() - start)
  print elapsed
  </code></pre>