globby

def verhoeff(string):
    string, c = list(string)[::-1], 0
    d = (
        (0,1,2,3,4,5,6,7,8,9),
        (1,2,3,4,0,6,7,8,9,5),
        (2,3,4,0,1,7,8,9,5,6),
        (3,4,0,1,2,8,9,5,6,7),
        (4,0,1,2,3,9,5,6,7,8),
        (5,9,8,7,6,0,4,3,2,1),
        (6,5,9,8,7,1,0,4,3,2),

globby

def table(sub):
    pos, cnd = 2, 0
    T = [-1,0]
    while pos < len(sub):
        if sub[pos-1] == sub[cnd]:
            cnd += 1
            pos += 1
            T.insert(pos,cnd)
        elif cnd > 0:
            cnd = T[cnd]

globby

def RabinKarp(string, sub):
    n, m = len(string), len(sub)
    for i in range(0,n-m+1):
        for j in range(0,m):
            if string[i+j] != sub[j]:
                break
        else:
            return i
    return -1

globby

def BinarySearch(lst, key):
    def Recurse(lst,key,low,high):
        if high < low:
            return -1
        m = (low + high) / 2
        if lst[m] > key:
            return Recurse(lst,key,low,m-1)
        elif lst[m] < key:
            return Recurse(lst,key,m+1,high)
        else:

globby

def BinarySearch(lst,key):
    low, high = 0, len(lst)
    while low <= high:
        m = (low + high) / 2
        if lst[m] > key:
            high = m - 1
        elif lst[m] < key:
            low = m + 1
        else:
            return m

globby

def BalancedBrackets(string):
    a = 0
    for x in string:
        a += 1 if x == '[' else -1 if x == ']' else 0
        if a < 0: return False
    return not a

globby

class MersenneTwister(object):
    def __init__(self,seed):
        self.MT = range(624)
        self.index = 0
        self.initialize(seed)
    def last32(self,num):
        return int(bin(num)[-32:],2)
    def initialize(self,seed):
        self.index = 0
        self.MT[0] = seed

globby

def Cocktail(lst):
    swapped = True
    while swapped:
        swapped = False
        for i in range(0,len(lst)-2):
            if lst[i] > lst[i+1]:
                lst[i], lst[i+1] = lst[i+1], lst[i]
                swapped = True
        if not swapped:
            break

globby

def combsort(lst):
    gap = len(lst)
    shrink = 1.3
    swapped = True
    while not (gap == 1 and not swapped):
        gap = int(gap/shrink)
        if gap < 1:
            gap = 1
        i = 0
        swapped = False

globby

def gnomesort(lst):
    pos = 1
    while pos < len(lst):
        if lst[pos] >= lst[pos-1]:
            pos += 1
        else:
            lst[pos], lst[pos-1] = lst[pos-1], lst[pos]
            if pos > 1:
                pos -= 1