[triangle-zpug] how to match strings in python

[Chris Calloway]

On 4/2/2009 3:15 PM, Chris Rossi wrote:
> I missed that the wikipedia algorithm was trying to solve a different
> problem: longest common string, not necessarily starting at 0.  I would have
> a tendency to solve this as a find string algorithm, attempting to find the
> shorter in the longer, keeping track of partial matches along the way.  I
> seem to recall seeing one that was O(n) in college, but I won't cheat and
> try and dig out that text book.  College was a long time ago, so I could
> easily be mistaken about O(n).

LCS is not possible in less than O(nm) for time. The wiki article 
suggests a change to make it the algorithm O(n) for storage by only 
storing one column of the array at a time.

-- 
Sincerely,

Chris Calloway
http://www.secoora.org
office: 332 Chapman Hall   phone: (919) 599-3530
mail: Campus Box #3300, UNC-CH, Chapel Hill, NC 27599