First different char in two strings?
Darrell Gallion
darrell at dorb.com
Tue May 23 00:29:40 EDT 2000
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