#!/usr/bin/python2.2

import random
import time

def prefix_linear(text1, text2):
  # Linear search.
  for i in xrange(0, len(text1)):
    if text1[i] != text2[i]:
      return i
  return len(text1)


def diff_commonPrefix(text1, text2):
  """Determine the common prefix of two strings.

  Args:
    text1: First string.
    text2: Second string.

  Returns:
    The number of characters common to the start of each string.
  """
  # Quick check for common null cases.
  if not text1 or not text2 or text1[0] != text2[0]:
    return 0
  # Binary search.
  pointermin = 0
  pointermax = min(len(text1), len(text2))
  pointermid = pointermax
  pointerstart = 0
  while pointermin < pointermid:
    if text1[pointerstart:pointermid] == text2[pointerstart:pointermid]:
      pointermin = pointermid
      pointerstart = pointermin
    else:
      pointermax = pointermid
    pointermid = int((pointermax - pointermin) / 2 + pointermin)
  return pointermid

# Create a random string of 'n' letters.
n = 10000
repeats = 100
text1 = ''
while len(text1) < n:
  text1 = text1 + chr(random.randrange(32, 127 - 32)) + text1
text1 = text1[:n]

# Create another random string which differs from the first by one letter inserted.
answer = random.randrange(0, n)
text2 = text1[:answer] + '\t' + text1[answer:]

startTime = time.time()
for x in range(repeats):
  result = prefix_linear(text1, text2)
endTime = time.time()
if result == answer:
  correct = 'OK'
else:
  correct = 'FAIL';
print "Linear: %fms (%s)" % ((endTime - startTime) * 1000 / repeats, correct)

startTime = time.time()
for x in range(repeats):
  result = diff_commonPrefix(text1, text2)
endTime = time.time()
if result == answer:
  correct = 'OK'
else:
  correct = 'FAIL';
print "Binary: %fms (%s)" % ((endTime - startTime) * 1000 / repeats, correct)