KMP字符串匹配算法

# -*- coding: utf-8 -*-
"""
Created on 2020-04-02 16:01:54

简介：KMP字符串匹配

@author: 杨h  yh4241@foxmail.com 
"""

def gen_pnext(substr):
    m = len(substr)
    pnext = [0]*m
    j = 0
    i = 1
    while i < m:
        if substr[j] == substr[i]:
            pnext[i] = j+1
            j += 1
            i += 1
        elif j != 0:
            j = pnext[j-1]
        else:
            pnext[i] = 0
            i += 1
    return pnext

gen_pnext('abcabgac')
# [out]:[0, 0, 0, 1, 2, 0, 1, 0]
def KMP_algh(string, substring):
    pnext = gen_pnext(substring)
    i, j = 0, 0
    n = len(string)
    m = len(substring)
    while j<m and i<n:
        if substring[j] == string[i]:
            j += 1
            i += 1
        elif j!=0:
            j = pnext[j-1]
        else:
            i += 1
    if j == m:
        return i-j
    else:
        return -1

KMP_algh('abgabcabgacyf','abcabgac')
#[out]:3

参考文章