def lines(b, a):
    a_split = a.split("\n")
    b_split = b.split("\n")
    count = 0
    for bs in b_split:
        if bs in a_split:
            count += 1
    return count

def compare(one, two):
    count = 0
    for l in iter(one.splitlines()):
        # two only contains the line
        # or 
        # two has the line, and lines under it
        # or
        # two has the line at the end, with other lines above
        if l == two or l + "\n" in two or two.endswith("\n" + l):
            count+=1

    #perc = int(count/len(one.splitlines())*100)

    return count

def memoize(function):
    from functools import wraps

    cache = {}

    @wraps(function)
    def wrapper(*args):
        if args in cache:
            return cache[args]
        else:
            rv = function(*args)
            cache[args] = rv
            return rv
    return wrapper


@memoize
def edit_distance(s1, s2): # optimized levenshtein distance
    if len(s1) > len(s2):
        s1, s2 = s2, s1

    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        distances = distances_
    return distances[-1]



# str1 = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum."
# str2 = "Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book."

# print(lines(str1, str2), "REGELS ZIJN HET ZELFDE")
# print(edit_distance(str1, str2), "LEVENSTEIN EDIT DISTANCE")