¶开始 Starting

此篇文字谨以记录关于KMP算法，必须写点什么巩固自己的印象

题目：https://leetcode-cn.com/problems/implement-strstr/

¶题目 Question

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

¶想法 Thinking

一开始想用Brutal-force，然不知为何python写的brutal force 竟然超时了。。。看题解发现有一个铭文KMP 的算法，遂再搜索一番，好好学习了一下

¶算法 Algorithm

首先暴力：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        i = 0
        if needle == '':
            return 0
        while i < len(haystack):
            if haystack[i:i+len(needle)] == needle:
                return i
            else:
                i+=1

        return -1

这里强烈推荐本视频https://www.youtube.com/watch?v=dgPabAsTFa8

配合这篇回答，https://www.zhihu.com/question/21923021，对KMP会有很好的理解

KMP算法主要包含两个主体：

由Partial Match Table 加以更改得到的Next table (prefix table)
调用Next table 的KMP 算法

¶Next table

¶前后缀

举个🌰子：

”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}

”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}

Note: 字符串本身并不是自己的前后缀。

¶PMT

Partial Match Table (PMT) 中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度.

例如，对于”aba”，它的前缀集合为{”a”, ”ab”}，后缀集合为{”ba”, ”a”}。两个集合的交集为{”a”}，那么长度最长的元素就是字符串”a”了，长度为1，所以对于”aba”而言，它在PMT表中对应的值就是1。再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}，两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。

如图 1.12 所示，要在主字符串"ababababca"中查找模式字符串"abababca"。如果在 len 处字符不匹配，那么由于前边所说的模式字符串 PMT 的性质，主字符串中 i 指针之前的 PMT[len −1] 位就一定与模式字符串的第 0 位至第 PMT[len−1] 位是相同的。这是因为主字符串在 i 位失配，也就意味着主字符串从 i−len 到 i 这一段是与模式字符串的 0 到 len 这一段是完全相同的。而我们上面也解释了，模式字符串从 0 到 len−1 ，在这个例子中就是”ababab”，其前缀集合与后缀集合的交集的最长元素为”abab”，长度为4。所以就可以断言，主字符串中i指针之前的 4 位一定与模式字符串的第0位至第 4 位是相同的，即长度为 4 的后缀与前缀相同。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将len指针指向模式字符串的PMT[len −1]位即可。

简而言之，首先进行普通匹配，发现在i，j处失配，因为PMT 的性质，我们知道模式字符串前6位的最长前后缀交集长度为4，因为模式字符串前j-1位都是匹配的，那么也就是说主字符串的后缀能够和模式字符串的前缀匹配上。那么自然而然的，图(a) 的灰色部分就不需要匹配了。相当于

图片在回答中查看

¶Next Table

next table 就是把pmt 给右移了，并且在第0个位置变成了 -1

图片在回答中查看

¶如何创建 next table

首先我们可以发现一个规律：如果列举出所有模式字符串的substring:

# Given: P= ABABCABA
# All possible substrings in a list :
A              #  substrings[0]     next table: 0
AB			   #  substrings[1]     next table: 0
ABA            #  substrings[2]     next table: 1
ABAB           #  substrings[3]     next table: 2
ABABC          #  substrings[4]     next table: 0
ABABCA         #  substrings[5]     next table: 1
ABABCAB        #  substrings[6]     next table: 2
ABABCABA       #  substrings[7]     next table: 3

如果已知某一个substrings[i] 的pmt 值，想得到 substrings[ i+1 ]的pmt 值，我们发现如果substrings[i+1] 的最后一位如果等于在substrings[i] 的pmt值所对应的那一位（把这个pmt当成index），那么 substrings[ i+1 ]的pmt 值等于substrings[i] 的pmt值+1。

也就是说，对于某个next table 中的值（称为 next），我们可以理解为包含当前字母的substring 的最长公共前后缀的大小，也可以表明当前substring 的第next-1 位字母和为最长公共前后缀的最后一个字母

栗子就是上面ABABCA 的pmt 是1，如果B == P[ABABCAB的pmt] 可以得到ABABCAB的pmt+1。

如果不相等，我们则回溯到len=next[len-1]。我们并非是在斜着对，目的是找到之前最长prefix里面的最长prefix是多少，从而判断最后加进来的那个字符可能组成为多长的新的prefix。例如 p = aaabaaaa这个例子，当倒数第一个a ，i=7， len=3，首先a不等于b，所以我们排除b，考虑 len= next[2] = 2 。记住，next表示的是最大前后缀，即aa为最大前后缀，此时p[i] == p[2] ，即next[i] = len+1!

这种创建方法可以参考上面贴的油管链接。

根据原理我们可以得到next:

def getNext(pattern: str) -> List[int]:
            next = [None] * len(pattern)
            next[0] = 0
            i = 1 # start from next[1]
            len = 0
            while i < len(pattern):
                if pattern[i] == pattern[len]: #next[1] = 0 
                    len+=1
                    next[i] = len
                    i+=1
                else:
                    if len>0:
                        len = next[len-1] #回溯到上一个
                    else:
                        next[i] = len # =0
                        i+=1
            # Right shift 1 
            i = len(next)-1
            while i > 0:
                next[i] = next[i-1]
                i-=1
            next[0] = -1
            return next

或者有种简单的想法：

其实，求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。

具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。在任一位置，能匹配的最长长度就是当前位置的next值。

Note: next 的第一位是被shift 得到的，一定为-1，第二位因为是求得于长度仅为1 的substring，必定此next 值为0。最后一位会被shift掉，所以也不用care\

总代码：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == "":
            return 0

        next = self.next_table(needle)
        i = 0 # for haystack
        j = 0 # for needle	
        while i < len(haystack):
            if j == len(needle) -1 and haystack[i] == needle[j]:
                return i-j
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            else:
                j = next[j]
                if j == -1:
                    i += 1
                    j += 1
        return -1



    def next_table(self, arr):
        next = [None] * len(arr)
        next[0] = 0
        # i represents the substring [0:i]
        i = 1
            # j represents the possible next value 
        j = 0
        while i < len(arr):
            if arr[i] == arr[j]:
                j+=1
                next[i] = j
                i+=1
            else:
                if j > 0:
                    j = next[j-1]
                else:
                    next[i] = j
                    i+=1
        # right shift
        i = len(next) - 1
        while i >= 0:
            next[i] =next[i-1]
            i-=1
        next[0] = -1
        return next

¶运行时间 Run-time

暴力算法 O(mn)

KMP算法 O(m+n)

¶反思 Introspection

需要多次复习加深印象

对于 getNext 的细节，需要多加复习

Algo

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

quick_sort/Netherland Flag Previous

Longest-Increasing-Subsequence Next