First different char in two strings?

Emile van Sebille emile at fenx.com
Tue May 23 03:58:20 CEST 2000


Ah, but with only a minor mod, time it again: ;-)

a = "abc"*
b = a[:-1]+'l'

for i in range(len(a)-1,0,-1):
  if b[i] != a[i]:
    break
print i

Life's-easier-when-you-get-to-select-the-test-case-ly y'rs,

Emile van Sebille
emile at fenx.com
-------------------


----- Original Message ----- 
From: Darrell Gallion <darrell at dorb.com>
To: <emile at fenx.com>
Cc: <python-list at python.org>
Sent: Monday, May 22, 2000 9:29 PM
Subject: Re: First different char in two strings?


> Emile wrote:
> > But, being as I generally find that the obvious way is often the
> > fastest,
> > or close enough, here's the obvious:
> > 
> > a = "this is a test"
> > b = "this is not a test"
> > for i in range(len(a)):
> >   if b[i] != a[i]:
> >     break
> > print i
> > 
> That was fun. The binary search won.
> 
> Output:
> 1499999
> 3.86000001431 Sec
> 1499999
> 0.468000054359 Sec
> 1499999
> 0.0939999818802 Sec
> ###########################################
> 
> import string, re
> 
> s1="abc"*500000
> s2 = s1[:]
> s2 = s1[:-1]+'l'
> 
> def algo1(a, b):
>     for i in range(len(a)):
>         if b[i] != a[i]:
>             return i
>     return -1
> 
> 
> def algo2(a, b, pat= re.compile("("+"."*1000+")")):
>     aS = pat.split(a)
>     bS = pat.split(b)
>     offset=0
>     for x in xrange(len(aS)):
>         if aS[x] != bS[x]:
>             i=offset+algo1(aS[x], bS[x])
>             return i
>         else:
>             offset=offset+len(aS[x])
>     return -1
> 
> def algo3(a, b):
>     aLen=len(a)
>     if aLen < 2:
>         if a[0] != b[0]:
>             return 0
>         if a[1] != b[1]:
>             return 1
>         return -1
> 
>     aLen=aLen/2
>     aL= a[:aLen]
>     bL= b[:aLen]
>     if aL==bL:
>         aH=a[aLen:]
>         bH=b[aLen:]
>         if aH==bH:
>             return -1
>         else:
>             return aLen+algo3(aH, bH)
>     else:
>         return aLen+algo3(aL, bL)
> 
> 
> import time
> t1=time.time()
> print algo1(s1, s2)
> print time.time()-t1
> 
> t1=time.time()
> print algo2(s1, s2)
> print time.time()-t1
> 
> t1=time.time()
> print algo3(s1, s2)
> print time.time()-t1
> 
> 
> 
> 





More information about the Python-list mailing list