kmb算法

[TOC]

kmp算法

kmp算法被用来做字符串的匹配。即 快速在 原字符串 中找到 匹配字符串

kmp算法的复杂度为O(m+n)

前缀： 包含首字母但不包含尾字母的所有子串。

后缀：包含尾字母但不包含首字母的所有子串。

匹配值为 前缀和后缀最大相同字串的长度

例：

 A B C C A B

前缀	后缀
A	B
AB	AB
ABC	CAB
ABCC	CCAB
ABCCA	BCCAB

匹配值为 2 （AB）

所以逐步获取 该字符串的匹配表为：

A	匹配值为 0
AB	0
ABC	0
ABCC	0
ABCCA	1
ABCCAB	2

基本思路

当发现某一个字符不匹配时，利用之前遍历过的字符信息来避免暴力算法中的 “回退” 的步骤.

KMP 算法通过生成的next 数组，当匹配失败时 看最后匹配成功的字符所对应的next 数值p。

将字串patt的指针返回到 patt [p] 。(p代表字串中可以跳过的字串个数，也即对应字串中的匹配值)

例：

主串 A B A B A B C A A

子串 [A B A B C]

NEXT [0 0 1 2 0]

A	B	A	B	A	B	C	A	A
A	B	A	B	C ×
0	0	1	2	0

当匹配到 子串 第一个数值时 发现不匹配。因此根据最后匹配成功的的字符 B 对应的next值 2 将指针指到 第2 个A 所在的位置继续匹配。（因为ABAB 匹配值为2 所以之前匹配成功的 AB 与 字串开头的两个 AB 完全一样，因此可以 跳过最长匹配字符 接着看之后数值是否匹配。）

A	B	A	B	A	B	C	A	A
		A	B	A	B	C
		0	0	1	2	0

不再需要回退主串中的指针，只需一次便利便可完成匹配 增加了效率

Next 数组 和 KMP算法实现

def build_next(patt):
    '''
    计算 Next数组
    '''
    next = [0] # next 数组(初值元素为0)
    prefix_len = 0 # 当前共同前后缀的长度
    i = 1
    while i < len(patt):
        if patt[prefix_len] == patt[i]:  #如果下个字符相同 即可构成更长度的前后缀
            prefix_len += 1
            next.append(prefix_len)
            i += 1
        else:
            if prefix_len == 0:
                next.append(0) #当查表后，依然不存在相应的 数值，则将对应next设为0
                i += 1
            else:
                prefix_len = next[prefix_len - 1] 
                # 当下一个字符不同时，前一个字符相同则只需查遍上一个字符相匹配的字符的后一个字符是否相同，看看是否有更短的前后缀
    return next

def kmp_search(string,patt): #时间复杂度为 O（n）
	next = build_next(patt)
    
    i = 0 #主串中的指针
    j = 0 #字串中的指针
    while i < len(string):
		if string[i] == patt[j]: #字符串匹配，指针后移
            i += 1
        	j += 1
        elif j > 0: #字负匹配失败，根据 next 跳过字串前面的一些字符
            j = next[j-1]
        else: # 子串第一个字符匹配失败
            i += 1
        if j == len(patt): #匹配成功
            return i-j
        

例题

28. 找出字符串中第一个匹配项的下标

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        def build_next(patt):
            '''
            计算 Next数组
            '''
            next = [0] # next 数组(初值元素为0)
            prefix_len = 0 # 当前共同前后缀的长度
            i = 1
            while i < len(patt):
                if patt[prefix_len] == patt[i]:  #如果下个字符相同 即可构成更长度的前后缀
                    prefix_len += 1
                    next.append(prefix_len)
                    i += 1
                else:
                    if prefix_len == 0:
                        next.append(0) #当查表后，依然不存在相应的 数值，则将对应next设为0
                        i += 1
                    else:
                        prefix_len = next[prefix_len - 1] 
                        # 当下一个字符不同时，查遍看看是否有更短的前后缀
            return next
        next = build_next(needle)
    
        i = 0 #主串中的指针
        j = 0 #字串中的指针
        while i < len(haystack):
            if haystack[i] == needle[j]: #字符串匹配，指针后移
                i += 1
                j += 1
            elif j > 0: #字负匹配失败，根据 next 跳过字串前面的一些字符
                j = next[j-1]
            else: # 子串第一个字符匹配失败
                i += 1
            if j == len(needle): #匹配成功
                return i-j
        if needle not in haystack:
            return -1