First different char in two strings?

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