tirgul12.py

import random

def hash_table(m):
    """ initial hash table, m empty entries """
    return [[] for i in range(m)]

def hash_mod(key, mod, func=hash):
    return func(key) % mod

def contained(candidate_key, list_of_items):
    """ checks if item is a member in list_of_items """
    for k in range(len(list_of_items)):
        if candidate_key == list_of_items[k]:
            return k
    return None

def find(candidate_key, table, h=hash, mod=0):
    """ returns item with candidate_key if table of size mod using hash func h, None otherwise """
    if mod == 0:
        mod = len(table)
    i = hash_mod(candidate_key, mod, h)
    list_of_items = table[i]
    k = contained(candidate_key, list_of_items)
    if k != None:
        return list_of_items[k]
    else:
        return None

def insert(item, table, h=hash, mod=0):
    """ insert an item into table of size mod using hash function h"""
    if mod == 0:
        mod = len(table)
    i = hash_mod(item, mod, h)
    if contained(item, table[i]) == None:
        table[i].append(item)
    return None

def repeat_hash2(st, l):
    h = set()
    for i in range(len(st) - l + 1):
        candidate = st[i:i+l]
        if candidate in h:
            return True
        h.add(candidate)
    return False

def repeat_hash(st, l):
    h = hash_table(len(st)-l)
    for i in range(len(st) - l + 1):
        candidate = st[i:i+l]
        if find(candidate, h):
            return True
        insert(candidate, h)
    return False

def repeat_naive(st, l):
    for i in range(len(st) - l + 1):
        for j in range(i + 1, len(st) - l + 1):
            if st[i:i+l] == st[j:j+l]:
                return True
    return False

def gen_str(size):
    """ Generate a random lowercase English string of length size"""
    s = ""
    for i in range(size):
        s += random.choice("abcdefghijklmnopqrstuvwxyz")
    return s