KMP python实现

首先去 https://blog.csdn.net/starstar1992/article/details/54913261/ 这里看下思想；

然后代码实现，一定要多调试几遍方能看懂：

def gen_pnext(p):

    i, k, m = 0, -1, len(p)

    pnext = [-1] * m   #初始化数组元素全为-1，-1表示当前元素之前的字符串相同的最大前缀和最大后缀元素个数

    while i < m-1:     #不能超过模式数组的长度

        print('i=',i)

        print('p[i]=',p[i])

        print('k=',k)

        print('p[k]=',p[k])

        print('pnext=',pnext)

        if k == -1 or p[i] == p[k]: #k=-1表示还没对相应位置的元素求移动量，

            # p[i]==p[k]表示当前元素与k位置元素相等（第一次时k肯定为0），

            # 然后i，k同时后移继续比较元素个数。

            # k=0表示前后最大相同字串个数为0，k=1表示有1个相同的，k=2表示有2个

            i, k = i+1, k+1

            pnext[i] = k

        else:

            k = pnext[k]

    return pnext

t = 'abbcabca'

p = 'abbcabc'

print(gen_pnext(p))

完整代码：

def matching_KMP(t, p, pnext):

    j, i = 0, 0

    n, m = len(t), len(p)

    while j < n and i < m:

        if i == -1 or t[j] == p[i]:

            j, i = j+1, i+1

        else:

            i = pnext[i]

    if i == m:

        return j - 1

    return -1

def gen_pnext(p):

    i, k, m = 0, -1, len(p)

    pnext = [-1] * m   #初始化数组元素全为-1，-1表示当前元素之前的字符串相同的最大前缀和最大后缀元素个数

    while i < m-1:     #不能超过模式数组的长度

        print('i=',i)

        print('p[i]=',p[i])

        print('k=',k)

        print('p[k]=',p[k])

        print('pnext=',pnext)

        if k == -1 or p[i] == p[k]: #k=-1表示还没对相应位置的元素求移动量，

            # p[i]==p[k]表示当前元素与k位置元素相等（第一次时k肯定为0），

            # 然后i，k同时后移继续比较元素个数。

            # k=0表示前后最大相同字串个数为0，k=1表示有1个相同的，k=2表示有2个

            i, k = i+1, k+1

            pnext[i] = k

        else:

            k = pnext[k]

    return pnext

t = 'abbcabca'

p = 'abbcabc'

print(gen_pnext(p))

print(matching_KMP(t,p,gen_pnext(p)))

如有疑问，欢迎留言！

巴特西

KMP python实现

最新文章

热门文章