KMP算法梳理

刷LeetCode算法题的时候，碰到了这个KMP。觉得还有点意思。相对来说还是有点难度，就做个笔记梳理一下。

---

KMP算法则可以将时间复杂度下降到O(m+n),和O(m*n)相比明显下降。

A，B 》 j，i 不等 为0 A，C 》 j，i 不等为0 一直到 A，A 》 j，i 相等记作1.然后同时进一位。B，B 》

j，i 相等 前位置加1 。C ， D不等，往前推。。A，D也不等，记作0

def KMP_algorithm(string, substring):
    '''
    KMP字符串匹配的主函数
    若存在字串返回字串在字符串中开始的位置下标，或者返回-1
    '''
    pnext = gen_pnext(substring)
    n = len(string)
    m = len(substring)
    i, j = 0, 0
    while (i<n) and (j<m):
        if (string[i]==substring[j]):
            i += 1
            j += 1
        elif (j!=0):
            j = pnext[j-1]
        else:
            i += 1
    if (j == m):
        return i-j
    else:
        return -1
            
    
def gen_pnext(substring):
    """
    构造临时数组pnext
    """
    index, m = 0, len(substring)
    pnext = [0]*m
    i = 1
    while i < m:
        if (substring[i] == substring[index]):
            pnext[i] = index + 1
            index += 1
            i += 1
        elif (index!=0):
            index = pnext[index-1]
        else:
            pnext[i] = 0
            i += 1
    return pnext

if __name__ == "__main__":
    string = 'abcxabcdabcdabcy'
    substring = 'abcdabcy'
    out = KMP_algorithm(string, substring)
    print(out)

和主字符串对比时，如果不同，看前一位pnext值对应的字母作为分隔线。为零，就是将整个字符串都后移。

参考文档：

b站视频很不错

python代码实现

阮一峰KMP