Text search (BF, BM, KMP)

def bruteForceSearch(wantedString, text):
    if len(wantedString) > len(text):
        return -1

    for i in range(len(text) - len(wantedString) + 1):
        p = True
        for j in range(len(wantedString)):
            if wantedString[j] != text[i + j]:
                p = False
                break

        if p == True:
            return i
            break

    return -1


def lastOccurence(string):
    table = {}

    for i in xrange(len(string)-1, -1, -1):
        if not string[i] in table:
            table.update({string[i]: i})

    return table

def BoyerMooreSearch(wantedString, text):
    table = lastOccurence(wantedString)

    i = j = len(wantedString) - 1

    while i < len(text):
        if wantedString[j] == text[i]:
            if j == 0:
                return i
            else:
                i -= 1
                j -= 1
        else:
            if text[i] in table:
                l = table[text[i]]
            else:
                l = -1

            i = i + len(wantedString) - min(j, l + 1)
            j = len(wantedString) - 1

    return -1


def failureFunction(string):
    array = []

    array.append(0)
    i = 1
    j = 0

    while i < len(string):
        if string[i] == string[j]:
            array.append(j + 1)
            i = i + 1
            j = j + 1
        elif j > 0:
            j = array[j-1]
        else:
            array[0] = 0
            i = i + 1

    return array

def KnuthMorrisPrattSearch(wantedString, text):
    FailureFunction = failureFunction(wantedString)
    i = j = 0
    while i < len(text):
        if text[i] == wantedString[j]:
            if j == len(wantedString) - 1:
                return i - j
            else:
                j = j + 1
                i = i + 1
        elif j > 0:
            j = FailureFunction[j - 1]
        else:
            i = i + 1

    return -1