title: Levenshtein Distance Algorithm better than O(n*m)?
body: <p>I have been looking for an advanced levenshtein distance algorithm, and <a href="http://www.levenshtein.net/" rel="noreferrer">the best I have found so far</a> is O(n*m) where n and m are the lengths of the two strings. The reason why the algorithm is at this scale is because of space, not time, with the creation of a matrix of the two strings such as this one:</p>
  
  <p><img src="https://i.stack.imgur.com/wYCIl.gif" alt="alt text"></p>
  
  <p><strong>Is there a publicly-available levenshtein algorithm which is better than O(n*m)?</strong> I am not averse to looking at advanced computer science papers &amp; research, but haven't been able to find anything. I have found one company, Exorbyte, which supposedly has built a super-advanced and super-fast Levenshtein algorithm but of course that is a trade secret. I am building an iPhone app which I would like to use the Levenshtein distance calculation. <a href="http://www.merriampark.com/ldobjc.htm" rel="noreferrer">There is an objective-c implementation available</a>, but with the limited amount of memory on iPods and iPhones, I'd like to find a better algorithm if possible.</p>