1、简介

从功能上来说, KMP算法实现的Java的indexOf函数, 实现Python的find函数, 用来查找某一子串在主串中出现的起始位置

2、暴力(Brute-Force)匹配

如下图, 模式串和主串进行逐位比较, 如果相等指针同时➕1, 如果发生失配, 则需要将主串指针向后移动一位, 这样会进行大量比较
时间复杂度: O(m * n ), m主串长度, n模式串长度

2.1 代码实现

	// 思路1: 暴力BF算法,   每次从text的p开始和mode逐位比较, 如果不匹配, 就更新 p++;
     public int strStr(String text, String mode) {
        if(mode.length() == 0)
            return 0;

        //p指向主串开始比较的位置, j进行逐位比较的循环指针
        int p = 0, j = -1;
        // 剩余区间小于 mode长度就不必再匹配了
        while(text.length() - p >= mode.length()){
           j = p;
           // 逐位比较成功直接返回p即可
           for(int i =0 ;i < mode.length();){
               if(text.charAt(j) == mode.charAt(i)){
                    if(i == mode.length() -1)
                        return p;

                    j++;
                    i++;
               }else{
                   break;
               }
           }
		   // 如果失配了, 更新主串开始比较的指针为下一位
           p++;
        }
        return -1;
    }
复制代码

3、KMP 算法 (Knuth-Morris-Pratt)

快速从主串中找出包含的模式串的位置的匹配算法.
该算法相对于 Brute-Force（暴力）算法有较大的改进，消除了主串指针的回溯
当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
KMP算法通过预处理提前计算好模式串每一个位置在失配的情况下一步该怎么走, 然后在和主串匹配过程发生失配就可以直接继续匹配不用从头开始匹配. 所以KMP主要研究的是模式串与主串是什么样的并不关心
而这个记录了模式串与主串不匹配的时候，模式串应该从哪里开始重新匹配的结构就叫做 Next数组
时间复杂度: O(m + n ), m主串长度, n模式串长度

3.1 算法原理

1、首先主串和模式串逐位比较, 如果匹配, 两个指针同时加1.
- 假设主串当前指针是 j , 模式串当前比较指针是i
2、而如果当前位置i 和 j 不匹配时, 模式串的比较指针i回退到模式串[0, i-1]之间的最长公共前后缀的长度的那个位置(即指向最长前缀的下一位), 此时再与主串的当前位置j继续进行比较. 如果还是不匹配, 重复2的过程. 直到回退到 i 和 j 匹配为止或者模式串比较指针i回退到了起始位置0.
3、发生不匹配后, 经过模式串指针的回退, 此时主串和模式串又可以愉快的进行逐位的比较了, 匹配就走1 过程. 不匹配就走2 的过程. 如果模式串比较指针 j 匹配到了结尾代表匹配成功.

整体失配匹配的过程

具体来看一次失配移动的过程

这个动图表示的是 “模式串的比较指针i回退到模式串[0, i-1]之间的最长公共前后缀的长度的那个位置(即指向最长前缀的下一位)” 这种效果
tip: 代码实现并不会真的去移动模式串, 所有的移动只是更新比较指针的位置而已

3.2 三个为什么

3.2.1 为什么模式串指针可以回退最长公共前后缀去继续匹配

假设某主串和模式串逐位比较到如下的情况, 假若此时 主串比较指针 i 和 模式串比较指针j发生不匹配. 如果按照暴力算法的思路, 此时主串比较指针j需要回退到主串索引1的位置, 模式串指针i需要回退到索引0到位置, 然后两者再继续从头开始逐位比较.

假设此时[0, i-1] 之间存在最长公共前后缀, 即ABA. 并且主串的最长公共前后缀是x1 和 x2, 模式串的最长公共前后缀是y1 和 y2, 并且x1 = x2( 是匹配的), y1 = y2, 并且由于[0, i-1] 和 [0, j-1] 是匹配的, 所以是不是有 x2 = y1 (是匹配的), 也就是说这部分y1和x2对于模式串和主串来说已经是匹配的就没有必要再继续进行匹配了, 所以我们只需要更新模式串的比较指针i到最长公共前后缀的长度的位置(即索引3的位置), 此时让它再去与主串的当前位置j继续进行比较即可, 如果匹配, 两个指针同时加1, 如果不匹配, 那么模式串指针i 同理继续回退.

最坏情况就是没有公共前后缀, 即模式串指针i 要回退到开头的位置从头去与主串的当前位置 j 继续比较. 所以即使这种最坏情况依旧比暴力匹配好, 因为主串比较指针并不用回退

3.2.2 这样更新模式串指针到底会不会漏掉一些情况?

直接更新模式串的指针i到最长公共前后缀的长度的位置到底会不会漏掉一些匹配的情况呢, 比如下图这种匹配情况

其实不会, 因为如果存在这种匹配情况,那么 x3 = y3(是匹配的), 而又因为 x3 和 y4在失配的时候本来就是匹配的, 所以最终导致 y3 = y4, 那么就说明应该此时会存在公共前后缀, 并且是最长的公共前后缀

3.2.3 为什么即使模式串指针回退到起始位置, 主串指针依然不用回退也可以继续匹配?

1、主串的比较指针从来不用回退, 那么中间有没可能漏掉了一些匹配的情况?

2、比如下图, 在G和F发生不匹配后因为没有公共前后缀, 模式串的比较指针 i 回退到了起始位置, 假设此时主串指针j 之前可能存在匹配的情况, 也就是如图可能会存在x2=y1(是匹配的)的这种情况, 但是其实这种情况是不可能发生的, 我们知道此时在位置j失配的情况下, x2 = y2(是匹配的). 所以如果存在x2=y1(是匹配的) , 那么 y1 和 y2 区域是匹配, 这不就是公共前后缀吗, 所以在没有公共前后缀的情况下, j之前的主串是没有与模式串前缀相匹配的, 所以主串指针j不用回退,直接从 j 开始继续比较即可.

斜着看, 更好理解为什么 x2 和 y1是匹配的, 这个的前提是基于我们之前的假设, 即此时主串指针j 之前可能存在匹配的情况(比如x2段)

3.2.4 如何计算Next数组

说白就是计算每个位置的最长公共前后缀的长度
关于Next数组的实现网上存在略微的偏差, 其实是因为定义的Next数组的具体意义不同, 但是它目标都是为了在当前位置失配的情况下, 下一步该怎么走. 通过提前预处理计算每一个位置失配情况
我这里对于Next数组的定义是: next[i] 表示 next[0, i] 之间的最长公共前后缀的长度, 它代表的实际意义是指向最长前缀的下一位

next数组理论计算过程

最长公共前后前后缀计算过程

实际上并不能肉眼就看出最长公共前后前后缀的长度是多少, 下面来看看具体如何去计算最长公共前后缀

原理

用 j 表示指向最长公共前缀的最后一位(前缀指针), i表示指向最长公共后缀的最后一位(后缀指针). 如果i 和 j 相等则前后缀指针同时+1, 如果不相等则需要回退前缀指针j 到上一个最长的前后缀长度的位置, 即 next[j-1]. 此时再比较j 和 i. 如果还是不匹配则前缀指针j 继续回退, 直到 j 和 i 相等或者回退到起点0. 最后前缀指针 j + 1的值就表示next[0, i] 之间的最长前后缀的长度, 它意义也表示指向最长前缀的下一位

为什么 j 回退到next[j-1]就可以计算出最长的前后缀 ?

假设此时前缀指针j 和后缀指针计算到了如下情况, 在j=7和i=14时发生了失配. 而之前的最长前后缀是ABCDABC, 所以需要找到此时next[0, i] 之间的新的最长前后缀是什么.

这时我们把前缀指针 j 回退到 next[j-1]的位置 , 如下图. next[j-1] 就表示next[0, j-1]之间的最长前后缀的长度(即指向最长前缀的下一位), 此时最长前缀X0的子最长前后缀分别是x1 和 x2 区域, 同理最长后缀Y0的子最长前后缀就是y1 和 y2, 而又因为X0 和 Y0 是匹配的, 所以有 X1 和 y2 是匹配的 所以此时再去比较 j 和 i 的值就可以知道此时next[0, i] 之间的最长前后缀的长度. 如果相等最长公共前后缀的长度就是 j + 1, 如果还是不相等, 继续回退j 重复上述过程.

再次回退后, j 和 i 还是不想等, j 回退到0, 还是不想等. 所以next[i] = 0

3.5 KMP代码实现

其实KMP的代码实现非常简短

def find(text, pattern) -> int:
    """
    :param text:            主串 
    :param pattern:         模式串
    :return: 
    """
    next: list = getNext(pattern)
    # 模式串指针
    j = 0
    
    # 遍历主串和模式串逐位匹配
    for i in range(len(text)):
        # 如果发生失配， 则模式串指针j需要根据next数据回退
        # 即回退到最长公共前缀的下一位， 即next[0,j-1]之间的最长公共前后缀的长度
        # j 直到回退到0 或者 j 和 i 相等
        while j > 0 and pattern[j] != text[i]:
            j = next[j-1]
        
        # 如果循环回退是因为j 和 i 相等退出，即模式串和主串当前位相等， 同时更新模式串指针j 和 主串指针i 即可
        if pattern[j] == text[i]:
            j += 1
            
            # 如果遍历到了模式串的末尾， 索命模式串完全匹配成功， 返回它在主串的开始索引即可
            if j == len(pattern):
                return i - j + 1

    return -1


def getNext(pattern: str) -> list:
    """ 计算next数组 """
    next: List[int] = [0] * len(pattern)
    next[0] = 0 # 0位置最长公共前后缀长度一定是0，直接赋值即可

    # 前缀指针
    j = 0

    # 计算每一个next[i], i同时表示后缀指针，不断+1， 不需要回退
    for i in range(1, len(next)):
        
        # 如果j 和 i不相等就一直回退， 直到相等或者 回退到起始位置
        while j > 0 and pattern[j] != pattern[i]:
            j = next[j-1]
        
        # j 和 i 分别指向前后缀的最后一位， 如果相等则next[i]的最长公共前后缀长度就是 j+1
        if pattern[j] == pattern[i]:
            next[i] = j + 1
            j += 1  # 更新前缀指针

    return next

字符串算法 | KMP算法动图详解