KMP字符串匹配算法

原创

一点一线

修改于 2022-03-26 17:27:08

8530

修改于 2022-03-26 17:27:08

文章被收录于专栏：计算机技术

KMP算法是很经典的字符串匹配算法，在字符的匹配过程中，只要遍历一次就可以找出所有的匹配串。对于超大型字符串来说，是一种非常高效的算法。KMP算法的核心是next数组。

next数组就是在遇到不匹配的字符时，匹配串应该从哪些一个字符开始与被匹配串开始进行比较。简单来说就是匹配串中哪些是重复出现的，记住这些重复出现的位置，重复的字符就不要比较了，从下一个不匹配的字符开始比较就可以。

下面举例来说明一下next数组

以字符串st= “stst1” 为例， next数组初始为[0，0，0，0，0]。

可以看到 s[0]=s[2], 对于如果s[3]位置不匹配时，只需要从比较s[1]的位置，因此next[3]=1。
同样s[1]=s[3], 在s[4] 不匹配的时候，只需要从s[2]开始比较，因此有next[4]=2。
所以next数组为[0，0，0，1，2]。

以python为例看一下next数组实现，以及匹配的实例

def get_next(st):
    n = len(st)
    next_arr = [0] * n
    index = 0
    for i in range(1, n):
        if st[i] == st[index]:
            index = index + 1
        else:
            index = 0
        next_arr[i] = index
    return next_arr


def match(src, dst, next_arr):
    j = 0
    count = 0
    for i in range(len(dst)):
        if dst[i] == src[j]:
            j = j + 1
        else:
            j = next_arr[j]
        if j == len(src):
            count = count + 1
            j = 0
            print(i, dst[i], count)


if __name__ == '__main__':
    arr = get_next("stst11stst11")
    match("stst11stst11", "kkkkstst11stst11ddddstst11stst11", arr)

运行结果：

[0, 0, 0, 1, 2, 0, 0, 1, 2, 3, 4, 5]

15 1 1

31 1 2

更多内容请关注微信公众号：IT技术漫漫谈

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python