First different char in two strings?

Darrell Gallion darrell at dorb.com
Tue May 23 06:44:09 CEST 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