# KMP字串搜索算法 (KMP algorithms)

KMP算法可以讓搜索字串的時間複雜度降低到 O(m+n)

[附上KMP詳解](https://www.youtube.com/watch?v=GTJr8OvyEVQ)

## 建立前綴索引

def builder(pattern: str) -> List[int]:
    i,j,n = 1,0,len(pattern)
    build = [0 for i in range(n)]
    while i < n:
        if pattern[i] == pattern[j]:
            build[i] = j + 1
            i += 1
            j += 1
        else:
            if j != 0:
                j = build[j-1]
            else:
                build[i] = 0
                i += 1
    return build

## 搜索

def finder(haystack: str,pattern: str) -> int:
    m = len(haystack)
    n = len(pattern)
    i = j = 0
    build = builder(pattern)
    output = []
    while m - j >= n - i: # haystack 要比 pattern 大
        if haystack[j] == pattern[i]:
            i += 1
            j += 1
        if i == n:
            output.append(j-i) # 返回相符字串第一個字的索引
            i = build[i-1]
        if j < m and haystack[j] != pattern[i]: # 不相等
            if i != 0:
                i = build[i-1]
            else:
                j += 1
    return output