Algorithm

Quote from COMP90038_2021_SM1: Algorithms and Complexity courseware, by Dr. Michael Kirley

ClosestPair

二维空间里n个点，找到一对距离最短的点

def ClosestPair(nodes):
    min = float("inf") //positive infinity
    n = len(nodes)
    for i in range(0, n - 1):
        xi, yi = nodes[i]
        for j in range(i + 1, n):
            xj, yj = nodes[j]
            d = ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5
            if d < min:
                min = d
                pi = i
                pj = j
    return pi, pj
def test():
    N = [(1, 3), (5, 8), (-2, 7), (-9, 0), (-4, -6)]
    print(ClosestPair(N))

StringMatching

很像KMP字符串匹配

def StringMatching(pattern, text):
    m = len(pattern)
    n = len(text)
    for i in range(0, n - m + 1):
        j = 0
        while j < m and pattern[j] == text[i + j]:
            j = j + 1
        if j == m:
            return i
    return -1
def test():
    print(StringMatching("hello", "abchellodef"))