[triangle-zpug] how to match strings in python

Stephan Altmueller stephan_altmueller at unc.edu
Thu Apr 2 19:10:34 UTC 2009

> On Thu, Apr 2, 2009 at 11:49 AM, Stephan Altmueller
> <stephan_altmueller at unc.edu <mailto:stephan_altmueller at unc.edu>> wrote:
>     Hi,
>     http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring#Python
> Wow, clearly implemented by a C programmer translating C directly to
> Python.  Love the opaque identifiers and the convoluted code.  Looks
> like he's creating a creating a 2 dimensional matrix of size
> len(string1) x len(string2)?!?!
> Is mine the shortest?  ;)
Clearly, I overshot on the difficulty of the actual problem that had to
be solved  ;-)

But it's a very different problem whether you are trying to find the
longest common
substring at the beginning of two strings or the longest common
substring in general
(where they can occur anywhere within the strings).

I don't see how you can implement the later without the two dimensional
which is necessary given the underlying dynamic programming algorithm.
Sometimes two dimensional arrays are actually pythonic ;-)

  -- Stephan

More information about the triangle-zpug mailing list