【python】python数据结构（三）——字符串：KMP算法的实现

我就是我 2022-06-07 13:49 75阅读 0赞

## 前言 ##

字符串是python中最常用也是最简单的数据结构，自带很多函数可以实现字符串的基本运算功能，本文介绍KMP算法实现字符串的匹配。

## KMP算法 ##

朴素匹配：将模式字符串p（长度为m）向目标字符串s（长度为n）上进行遍历匹配，即固定s，将s和p左对齐，之后一次移动p，如果对齐部分完全一样，则匹配成功，否则失败。朴素匹配的时间复杂度为O(mxn)。

KMP匹配：在匹配过程中，可以遵循一些规律来减少匹配次数，如模式串'asdfasd'向目标串'afdsgdasdhasdfasdc'做匹配，初始状态下进行匹配

## 算法实现 ##

# coding:utf-8
    
    #朴素匹配
    def naive_match(s, p):
        m = len(s); n = len(p)
        for i in range(m-n+1):#起始指针i
            if s[i:i+n] == p:
                return True
        return False
    
    #KMP
    def kmp_match(s, p):
        m,n = len(s),len(p)
        cur = 0#起始指针cur
        table = partial_table(p)
        while cur<=m-n:
            for i in range(n):
                if s[i+cur]!=p[i]:
                    cur += max(i - table[i-1], 1)#有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位
                    break
            else:
                return True
        return False
    
    #部分匹配表
    def partial_table(p):
        '''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''
        prefix = set()
        postfix = set()
        ret = [0]
        for i in range(1,len(p)):
            prefix.add(p[:i])
            postfix = {p[j:i+1] for j in range(1,i+1)}
            ret.append(len((prefix&postfix or {''}).pop()))
        return ret
    
    print naive_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")
    print partial_table("ABCDABD")
    print kmp_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")