KMP算法

kmp算法主要解决的问题就是字符串匹配，本篇文章节选自我的LeetCode字符串，在此单独记录一下kmp算法

题1:字符串匹配

寻找匹配子串，并返回起始索引

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        start = -1
        i = 0
        j = 0
        while i <= len(haystack)-len(needle):
            k = i
            while j < len(needle) and k < len(haystack) and haystack[k] == needle[j]:
                k += 1
                j += 1
            if j == len(needle):
                start = i
                break
            j = 0
            i += 1
        return start

最容易想到的暴力解法，文本串指针一位位向后移动，看是否匹配模式串，这种解法的算法复杂度是 O ( n × m ) O(n \times m) O(n×m)，因为对于文本串的每个字符，最多匹配 m m m次（ m m m为模式串的长度）

KMP算法

解决字符串匹配问题

思想：当文本串与模式串不匹配时，尽量减少模式串与文本串的匹配次数，避免文本串的回退，优化算法的时间复杂度

启发

普通的匹配算法，当我的文本串"aabaabaaf"去匹配模式串"aabaaf"的时候，第一次匹配，文本串指针从i = 0一路匹配到i = 5，模式串指针从j = 0匹配到j = 5最后一个f ≠ \neq = b，匹配失败了，文本串指针回退到i = 0 + 1，模式串指针回退到j = 0

这种匹配算法对于文本串的每个字符，最多匹配 m m m次（ m m m为模式串的长度），所以算法总的时间复杂度为 O ( n × m ) O(n \times m) O(n×m) n n n为文本串长度

但很明显，已经匹配的字符串中仍然含有信息没有被充分利用。比如上述例子中，完全不必要从文本串的i = 1开始匹配，因为i = 1开头之后只包含一个a，肯定无法匹配模式串，由于aabaa这个部分文本串已经被我们检测过了，应该要充分利用已经检测过的文本串的信息，实际上后面两个a可以对应模式串开头的两个a，所以模式串待匹配的部分从aabaa缩小为baaf，而文本串指针无需回退，从当前位置i = 5开始，继续向后移动，寻找baaf模式

kmp

数学原理

假设文本串长度为 n n n，模式串长度为 m m m，目前正在匹配 T [ i : i + m ] T[i:i+m] T[i:i+m]，不匹配发生在模式串的下标 j j j处，文本串记为 T T T(text)，模式串记为 P P P(pattern)

T [ i : i + j ] = = P [ 0 : j ] T[i:i+j] == P[0:j] T[i:i+j]==P[0:j] 注意python的区间是左闭右开
如果模式串 p p p的子串 p [ 0 : j ] p[0:j] p[0:j]具有对称性，即 p [ 0 : k ] = = p [ j − k : j ] p[0:k] == p[j-k:j] p[0:k]==p[j−k:j]，前k位和后k位相同
由 T [ i + j − k : i + j ] = = p [ j − k : j ] T[i+j-k:i+j] == p[j-k:j] T[i+j−k:i+j]==p[j−k:j]推出 T [ i + j − k : i + j ] = = p [ 0 : k ] T[i+j-k:i+j] == p[0:k] T[i+j−k:i+j]==p[0:k]，说明可以直接跳过对模式串的前 k k k位的匹配
可以直接将文本串 T [ i + j ] T[i+j] T[i+j]对准模式串 p [ k ] p[k] p[k]继续进行匹配

前缀后缀

前缀：不包含最后一个字符的所有以第一个字符开头的连续子串
后缀：不包含第一个字符的所有以最后一个字符结尾的连续子串

e.g对于"aabaaf"来说

前缀

a
aa
aab
aaba
aabaa

后缀

f
af
aaf
baaf
abaaf

前缀表 next数组

本质为求模式串的每个子串的对称性，求使得「前 k 个字符」恰好等于「后 k 个字符」的「最长的 k」

next[j] ： p [ 0 : j + 1 ] p[0:j + 1] p[0:j+1]子串中最长相等前后缀的长度，python为左闭右开区间，next数组记录到j为止的模式串子串中最长相等前后缀

e.g p = "aabaaf"

next[0] = 0，因为 "a" 中无有相同前缀后缀，最大长度为 0
next[1] = 1，因为 "aa" 中有相同前缀后缀"a"，最大长度为 1
next[2] = 0，因为 "aab" 中无相同前缀后缀，最大长度为 0
next[3] = 1，因为 "aaba" 中有相同的前缀后缀 "a"，最大长度为 1
next[4] = 2，因为 "aabaa" 中有相同的前缀后缀 "aa"，最大长度为 2
next[5] = 0，因为 "aabaaf" 中无相同前缀后缀，最大长度为 0

每次遇到不匹配之后在模式串中j指针从j = next[j-1]开始匹配，j-1是已经匹配的子串中最长相等前后缀长度

计算`next`数组

right每次指向当前要计算的子串末尾，长度为1的子串不用计算，最长相等前后缀一定是0
根据对称性，left指向匹配的前缀数量，等于匹配的后缀数量，所以可以直接next[right] = left
left = next[left - 1]匹配不成功的时候，left的更新是关键：相当于在计算next数组的时候也用了kmp思想
目前 p [ r i g h t ] ≠ p [ l e f t ] p[right] \neq p[left] p[right]=p[left]，根据前面的匹配过程 p [ 0 : l e f t ] = = p [ r i g h t − l e f t : r i g h t ] p[0:left] == p[right -left :right] p[0:left]==p[right−left:right]，left为前缀末尾right为后缀末尾
取t = next[left-1]，相当于在求子串 p [ 0 : l e f t ] p[0:left] p[0:left]有没有对称性，也就是在求 p [ r i g h t − l e f t : r i g h t ] p[right -left :right] p[right−left:right]的对称性
已知 p [ 0 : t ] = = p [ l e f t − t : l e f t ] p[0:t] == p[left-t:left] p[0:t]==p[left−t:left]
则根据 p [ 0 : l e f t ] = = p [ r i g h t − l e f t : r i g h t ] p[0:left] == p[right -left :right] p[0:left]==p[right−left:right]
得到 p [ r i g h t − l e f t : r i g h t − l e f t + t ] = = p [ r i g h t − t : r i g h t ] p[right-left:right-left+t] == p[right - t:right] p[right−left:right−left+t]==p[right−t:right]
再次根据 p [ 0 : l e f t ] = = p [ r i g h t − l e f t : r i g h t ] p[0:left] == p[right -left :right] p[0:left]==p[right−left:right]
得到 p p [ 0 : t ] = = p [ r i g h t − l e f t : r i g h t − l e f t + t ] = = p [ r i g h t − t : r i g h t ] pp[0:t] == p[right-left:right-left+t] == p[right - t:right] pp[0:t]==p[right−left:right−left+t]==p[right−t:right]
所以 p [ 0 : r i g h t ] p[0:right] p[0:right]子串拥有长度为 t t t的子区间，left不需要回退到起点开始计算

def creatNext(p:str):
    m = len(p)
    next = [0] * m #初始化next数组
    left = 0
    for right in range(1,m):
        while left > 0 and p[left] != p[right]:
            left = next[left-1]
        if p[left] == p[right]:
            left += 1
        next[right] = left
    return next

完整匹配过程

class Solution:
    def creatNext(self, p:str) -> list:
        m = len(p)
        next = [0] * m #初始化next数组
        left = 0
        for right in range(1,m):
            while left > 0 and p[left] != p[right]:
                left = next[left-1]
            if p[left] == p[right]:
                left += 1
            next[right] = left
        return next

    def strStr(self, haystack: str, needle: str) -> int:
        m = len(needle)
        j = 0  #j是模式串指针，i是文本串指针
        start = -1
        next = self.creatNext(needle)
        for i in range(len(haystack)):
            while j > 0 and haystack[i] != needle[j]:
                j = next[j-1]
            if haystack[i] == needle[j]:
                j += 1
            if j == m:
                start = i - j +1
                break
        return start

注意：

while j > 0 and haystack[i] != needle[j]:循环的时候别忘了j == 0是边界
while j > 0 and haystack[i] != needle[j]:循环一定要放在最前面，因为若当前haystack[i] == needle[j]的时候需要执行j + 1的，否则导致haystack[i] 和 needle[j] 的匹配被跳过

题2：重复的子字符串

给定一个非空的字符串s，检查是否可以通过由它的一个子串重复多次构成

不用KMP的暴力解法，尝试所有可能的子串 O ( n 2 ) O(n^2) O(n2)

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        for i in range(1,len(s)//2 + 1):
            # 子串的长度
            if len(s) % i != 0:
                continue
            flag = True
            for j in range(0,len(s),i):
                # 检验是否都能由这个子串构成
                if s[j:j+i] != s[0:i]:
                    flag = False
                    break
            if flag:
                return True
        return False

移动匹配，利用数学原理，调用库函数，库函数的实现是类KMP算法 O ( n + m ) O(n+m) O(n+m)

利用数学性质“周期性”化简程序设计思路，假设字符串 s s s的长度为 n n n，子字符串的长度为 k k k，注意， n = k × t n = k \times t n=k×t， n n n一定能被 k k k整除， t t t代表重复次数 t ≥ 2 t \geq 2 t≥2

s = s u b × t s = sub \times t s=sub×t sub是子字符串

当把字符串拼接起来并去除首尾的的时候 ( s + s ) [ 1 : − 1 ] = s u b [ 1 : ] + s u b × ( t − 1 ) + s u b × ( t − 1 ) + s u b [ : − 1 ] = s u b [ 1 : ] + s u b × ( 2 t − 2 ) + s u b [ : − 1 ] (s+s)[1:-1] = sub[1:] + sub \times (t-1) + sub \times (t-1) + sub[:-1] = sub[1:] + sub \times (2t - 2) + sub[:-1] (s+s)[1:−1]=sub[1:]+sub×(t−1)+sub×(t−1)+sub[:−1]=sub[1:]+sub×(2t−2)+sub[:−1] 由于 t ≥ 2 t \geq 2 t≥2所以 2 t − 2 ≥ t 2t - 2 \geq t 2t−2≥t，拼接之后的字符串中间一定包含至少一个s

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        joint = (s + s)[1:-1]
        idx = joint.find(s)
        if idx == -1:
            return False
        else:
            return True

直接使用KMP

Math again!

字符串 s s s的最长相等前后缀不包含的子串，若其长度能被 s s s整除，则这个不被包含的子串就是 s s s的最小重复子串

数学证明：“周期性”

假设字符串 s s s的本身的长度为 n n n，最长相等前后缀的长度为 m m m，不被包含的子串长度为 k = n − m k = n - m k=n−m
根据最长相等前后缀的定义， s [ 0 : m ] = = s [ n − m : n ] s[0:m] == s[n-m:n] s[0:m]==s[n−m:n]，因此 s [ 0 : k ] = = s [ n − m : n − m + k ] = s [ k : 2 k ] s[0:k] == s[n-m: n-m+k] = s[k:2k] s[0:k]==s[n−m:n−m+k]=s[k:2k]
同理 s [ k : 2 k ] = s [ n − m + k : n − m + 2 k ] = s [ 2 k : 3 k ] s[k:2k] = s[n-m+k:n-m+2k] = s[2k:3k] s[k:2k]=s[n−m+k:n−m+2k]=s[2k:3k]
以此类推，如果 m ∣ n m \mid n m∣n m m m可以被 n n n整除，则长度为 k k k的子串可以重复覆盖整个字符串 s s s

？为什么 s [ 0 : k ] s[0:k] s[0:k]就一定是最小重复子串呢？会不会存在比 s [ 0 : k ] s[0:k] s[0:k]更小的重复子串呢

假设存在更小的重复子串 s = s [ 0 : l ] × t s = s[0:l] \times t s=s[0:l]×t l ≤ k l \leq k l≤k
λ = n − l \lambda = n - l λ=n−l 则 s [ 0 : λ ] = = s [ 0 : l ] × ( t − 1 ) s[0:\lambda] == s[0:l] \times (t-1) s[0:λ]==s[0:l]×(t−1) s [ n − λ : n ] = = s [ l : n ] = s [ 0 : l ] × ( t − 1 ) s[n-\lambda:n] == s[l:n] = s[0:l] \times (t-1) s[n−λ:n]==s[l:n]=s[0:l]×(t−1)
所以推导出 s [ 0 : λ ] = s [ n − λ : n ] s[0:\lambda] = s[n-\lambda:n] s[0:λ]=s[n−λ:n] 存在更长的相等前后缀，长度为 n − λ n - \lambda n−λ

所以没有更小的重复子串是由我们求的是最长相等前后缀这一点保证的

要求最长相等前后缀的长度，直接去next数组的尾部寻找就行啦～因为next数组每个位置上求的是子串的最长相等前后缀，如果想求整个 s s s的最长相等前后缀，当然要去最后找啦

class Solution:
    def createNext(self, s:str) -> list:
        next = [0] * len(s)
        left = 0
        for right in range(1,len(s)):
            while left > 0 and s[left] != s[right]:
                left = next[left-1]
            if s[left] == s[right]:
                left += 1
            next[right] = left
        return next
    def repeatedSubstringPattern(self, s: str) -> bool:
        next = self.createNext(s)
        print(next)
        n = len(s)
        k = n - next[-1]
        if n % k == 0 and k < n:
            return True
        return False

*参考资料|代码随想录

标签：子串,right,匹配,后缀,next,算法,KMP,left
From： https://blog.csdn.net/CinderGirl/article/details/145205291

KMP算法

KMP算法

题1:字符串匹配

KMP算法

启发

数学原理

前缀后缀

前缀表 next数组

计算`next`数组

完整匹配过程

题2：重复的子字符串

不用KMP的暴力解法，尝试所有可能的子串 O ( n 2 ) O(n^2) O(n2)

移动匹配，利用数学原理，调用库函数，库函数的实现是类KMP算法 O ( n + m ) O(n+m) O(n+m)

直接使用KMP

相关文章

赞助商

阅读排行

KMP算法

KMP算法

题1:字符串匹配

KMP算法

启发

数学原理

前缀后缀

前缀表 next数组

计算next数组

完整匹配过程

题2：重复的子字符串

不用KMP的暴力解法，尝试所有可能的子串 O ( n 2 ) O(n^2) O(n2)

移动匹配，利用数学原理，调用库函数，库函数的实现是类KMP算法 O ( n + m ) O(n+m) O(n+m)

直接使用KMP

相关文章

赞助商

阅读排行

计算`next`数组