# 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 != b:
return 0
if a != b:
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

```