First different char in two strings?
Darrell Gallion
darrell at dorb.com
Tue May 23 00:44:09 EDT 2000
Bug fix:
When the difference was at position zero the last version gave the wrong
answer.
********
1499999
3.82799994946 sec
1499999
0.125 sec
********
0
0.453999996185 sec
0
0.0310000181198 sec
********
5
0.453999996185 sec
5
0.0149999856949 sec
********
750000
2.11000001431 sec
750000
0.0620000362396 sec
import string, re
import time
s1="abc"*500000
s2 = s1[:]
s2 = s1[:-1]+'l'
s3 = 'v'+s1[:-1]+'l'
s4 = s1[:5]+'l'
s5 = s1[len(s1)/2]+'l'
testList=[s2,s3,s4,s5]
def algo1(a, b):
for i in range(len(a)):
if b[i] != a[i]:
return i
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 algo3(aL, bL)
def timeTest(s1, s2):
t1=time.time()
print algo1(s1, s2)
print time.time()-t1, "sec"
t1=time.time()
print algo3(s1, s2)
print time.time()-t1, "sec"
for sN in testList:
print "********"
timeTest(s1, sN)
More information about the Python-list
mailing list