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&#39;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).<br>

<br>Chris Calloway&#39;s is pretty good--he beats wikipedia in terms of storage efficiency, but the wikipedia implementation is more processor efficient.  The wikipedia implementation is also a bit harder to grok, but this could be helped with comments and meaningful identifiers: also very Pythonic!<br>

<br>I don&#39;t think I can do better at the moment.  One could use your algorithm of choice for longest match starting at 0 and simply run that starting at different indices into the longer of the two strings.  This also gives O(n*m) performance.  I&#39;m sure I could figure out how to use zip() in there, but it wouldn&#39;t be any cleaner/nicer than what has already been presented, unless splitting it up into two functions makes it somewhat more readable.<br>
<br>Chris<br><br><br><div class="gmail_quote">On Thu, Apr 2, 2009 at 2:23 PM, Chris Calloway <span dir="ltr">&lt;<a href="mailto:cbc@unc.edu" target="_blank">cbc@unc.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

<div>On 4/2/2009 11:50 AM, Sam Brauer wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Sometimes I love little exercises like this.<br>
</blockquote>
<br></div>
I like doing this as a hive mind, because we can not only learn, but come up with more optimal solutions from what we all know together.<br>
<br>
I like Chris Rossi&#39;s zip solution, because that was especially Pythonic functional thinking which we should all be doing as it produces the most obviously elegant *and* efficient solutions.<br>
<br>
I like Stephan pointing out the LCS alorithm, because it solves a superset of what Joe said he was looking for (the longest part of one string anywhere within the other).<br>
<br>
I like what Sam did because it inspired me to do an LCS using the find string method and slices to do the heavy lifting. It&#39;s not as O(nm) efficient as the solution in the Algorithms book. But I think it&#39;s more understandable:<br>


<br>
def inCommonNG(string1, string2):<br>
    &quot;&quot;&quot;Finds first longest common string.&quot;&quot;&quot;<br>
    result = &#39;&#39;<br>
    if len(string1) &lt; len(string2):<br>
        shorter = string1<br>
        longer = string2<br>
    else:<br>
        shorter = string2<br>
        longer = string1<br>
    while shorter:<br>
        backup = shorter<br>
        start = longer.find(shorter)<br>
        while(start &lt; 0):<br>
            shorter = shorter[:-1]<br>
            start = longer.find(shorter)<br>
        if len(shorter) &gt; len(result):<br>
            result = shorter<br>
        shorter = backup[1:]<br>
        if len(shorter) &lt;= len(result):<br>
            break<br>
    return result<br>
<br>
print inCommonNG(&quot;foobar&quot;,&quot;foobaz&quot;)<br>
print inCommonNG(&quot;foobarrrr&quot;,&quot;foobaz&quot;)<br>
print inCommonNG(&quot;foobar&quot;,&quot;foobazzzz&quot;)<br>
print inCommonNG(&quot;foobar&quot;,&quot;&quot;)<br>
print inCommonNG(&quot;&quot;,&quot;foobaz&quot;)<br>
print inCommonNG(&quot;&quot;,&quot;&quot;)<br>
print inCommonNG(&quot;foobar&quot;,&quot;snafoobazsna&quot;)<br>
print inCommonNG(&quot;snafoobarsna&quot;,&quot;foobaz&quot;)<br>
print inCommonNG(&quot;snufoobarsnu&quot;,&quot;snafoobazsna&quot;)<br>
print inCommonNG(&quot;foobar&quot;,&quot;foobar&quot;)<br>
<br>
Produces:<br>
<br>
&gt;&gt;&gt;<br>
fooba<br>
fooba<br>
fooba<br>
<br>
<br>
<br>
fooba<br>
fooba<br>
fooba<br>
foobar<br>
&gt;&gt;&gt;<br>
<br>
Note, this algorithm finds the *first* LCS. There may be more than one.<br>
<br>
Note, this algorithm only works because of the hack in the find string method which returns 0 instead of -1 when the match string is empty. A useful and expected hack, that is.<br>
<br>
I bet Rossi can do this more efficiently with zip. :)<div><br>
<br>
-- <br>
Sincerely,<br>
<br>
Chris Calloway<br>
<a href="http://www.secoora.org" target="_blank">http://www.secoora.org</a><br>
office: 332 Chapman Hall   phone: (919) 599-3530<br>
mail: Campus Box #3300, UNC-CH, Chapel Hill, NC 27599<br>
<br>
<br>
<br>
<br>
_______________________________________________<br></div><div><div></div><div>
triangle-zpug mailing list<br>
<a href="mailto:triangle-zpug@starship.python.net" target="_blank">triangle-zpug@starship.python.net</a><br>
<a href="http://starship.python.net/mailman/listinfo/triangle-zpug" target="_blank">http://starship.python.net/mailman/listinfo/triangle-zpug</a><br>
</div></div></blockquote></div><br>