substringMatching.py

import string
import time

def sliceAt(s, i):
    return s[:i] + "[" + s[i] + "]" + s[i + 1:]

def hasSubstring1(key, text):
    return key in text

def hasSubstring2(key, text):
    if key == "":
        return True
    while(len(key) <= len(text)):
        if key == text[:len(key)]:
            return True
        text = text[1:]
    return False

def hasSubstring3(key, text):
    if key == "":
        return True
    for i in range(len(text) - len(key) + 1):
        if text[i:i + len(key)] == key:
            return True
        
    return False

def hasSubstring4(key, text):
    if key == "":
        return True
    for i in range(len(text) - len(key) + 1):
        isSubstring = True
        for j in range(len(key)):
            if key[j] != text[i + j]:
                isSubstring = False
                break
        if isSubstring:
            return True
        
    return False

def kmp(key, text):
    # 1. Compute Table
    table = [0] * len(key)
    for i in range(2, len(key)):
        nextPartialMatch = table[i - 1]
        while(1 == 1):
            if key[nextPartialMatch] == key[i - 1]:
                table[i] = nextPartialMatch + 1
                break
            if (nextPartialMatch == 0):
                table[i] = 0
                break
            nextPartialMatch = table[nextPartialMatch]
    
    # 2. Find substring
    i = ki = 0
    while(i < len(text)):
        # Visaul logging to see how it works
        # print "\nLooking at with ki="+ki, "and i="+i
        # print " "*(i-ki) + sliceAt(key, ki)
        # print sliceAt(text, i)
        if key[ki] == text[i]:
            i += 1
            ki += 1
            if ki == len(key):
                return True
            continue
        if ki > 0:
            ki = table[ki]
        else:
            i += 1
    return False

def timing(f):
    def wrap(*args):
        time1 = time.time()
        ret = f(*args)
        time2 = time.time()
        print '%s function took %0.3f ms' % (f.func_name, (time2 - time1) * 1000.0)  # + " for", args
        return ret
    return wrap

key_list = ['power', 'house', 'waterloo', 'erhou', 'a', 'h', 'water', 'r' * 15, 'comp', 'science', 'x' * 15, 'xxxscienceyyy', 'abcdabc', 'abcabcbabcbabcba', 'these', 'words', 'to', 'test', 'poop']
text_list = ['waterloo is a computer science powerhouse', "rrrrrrrrrr xxxxxxxxx rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx", "you abcdabx or helabcdabclo",
             "rrrrrrrrrrrrrrrrrrr "*600, "abcdab"*100 + "a"]
func_list = map(timing, [hasSubstring1, hasSubstring2, hasSubstring3, hasSubstring4, kmp])
def testHarness():
    for text in text_list:
        print '.::|| text is', repr(text)
        for func in func_list:
             for key in key_list:
                result = func(key, text)
                expected = key in text
                if result != expected:
                    print ">>>ERROR actual:%d expected:%d func:%s key:%r" % (result, expected, func.__name__, key)
testHarness()