大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
本文的逻辑顺序为

1、最基本的朴素算法

2、优化的KMP算法

3、应算法需要定义的next值

4、手动写出较短串的next值的方法

5、最难理解的、足足有5行的代码的求next值的算法

所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：


这个算法简单，不多说，附上代码
#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
    if(sLen<pLen)return 0;
    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
        if(s[i]==p[j]){i++;j++;}
        else{
            i = i-j+2;
            j = 1;
        }
    }
    if(j>pLen) return i-pLen;
    return 0;
}
void main(){
    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
    char p[]={' ','a','b','a','a','b','c','a','c'};
    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
}

三、改进的算法——KMP算法
朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。

一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。

朴素算法中，P的第j位失配，默认的把P串后移一位。

但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：


这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
相比朴素算法：

朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)

KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S[i]与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）


比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的




假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”




那么可以推出，P1…Pk-1与Si…Si+j-2




显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：




为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。


最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。


四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：



这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：


五、求next的算法
终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
    int i = 1,j = 0;
    while(i<=cLen){
        if(j==0||ch[i]==ch[j]) next[++i] = ++j;
        else j = next[j];
    }
}



还是先由一般再推优化：

直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）

根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。

不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：

if(P1…Pj-1 == P2…Pj)    => next[j+1]=j

else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1

else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2

…

…

…

else if(P1P2 == Pj-1Pj) => next[j+1]=3

else if(P1 == Pj-1) => next[j+1]=2

else if(P1 != Pj-1) => next[j+1]=1

每次前去尾1个，后掐头1个，直至得到next[j+1]


再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。

但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，

①next[j+1]的可能的最大值是多少（即从哪开始验证）

②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）

看一下的分析：


1、next[j+1]的最大值为next[j]+1。

因为：

假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。

如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1

2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]

这里不好解释，直接看下面的流程分析及图解
开——始——划——重——点！

从头走一遍流程

①求next[j+1]，设值为m

②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1

③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则

④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1

⑤第二第三步联合得到:

P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合

⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 =  Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：

1、要求next[k+1] 其中k+1=17



2、已知next[16]=8，则元素有以下关系：



3、如果P8=P16，则明显next[17]=8+1=9

4、如果不相等，又若next[8]=4，则有以下关系



又加上2的条件知



主要是为了证明：



5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推

6、若next[4]=2，则有以下关系



7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！

在关于字符串定位的算法中，朴素模式匹配算法极其低效。在很多年前我们的科学家们，觉得像有多个重复字符的字符串， 却需要挨个遍历的算法是非常糟糕的事情。 于是有三位前辈， D.E.Knutb、****J.H.Morris和 V.R.Pratt（其中Knuth 和Pratt共同研究， Morris独立研究）发表了一个模式匹配算法，可以大大避免重复遍历的情况， 我们把它称之为克努特一莫里斯—普拉特算法， 简称KMP算 法。

朴素模式匹配算法与KMP模式匹配算法的原理不在此说明。以下为利用Java语言实现的KMP算法的代码。
import java.util.*;

public class kmp{
	//计算要匹配的串T的next数组
	public void getNext(String T,int[] next) {
		int i = 0;
		int j = -1;
		next[0] = -1;
		while(i < T.length()-1) {
			if (j == -1||T.charAt(i) == T.charAt(j)) {
				++i;
				++j;
				next[i] = j;
			}else
				j = next[j];
		}
	}
	
	public int Kmp(String S,String T) {
		int i = 0;
		int j = 0;
		int sl = S.length();
		int tl = T.length();
		int[] next = new int[tl];
		getNext(T,next);
		while(i < sl && j < tl) {
			if(S.charAt(i) == T.charAt(j)) {
				i++;
				j++;
			}else {
				if (next[j] == -1) {
					i++;
					j = 0;
				}else {
					j = next[j];
				}
			}
			if (j >= tl) {
				return i-tl+1;
			}
		}
		return -1;	
	}
	public static void main(String[] args) {
		kmp k = new kmp();
		Scanner in = new Scanner(System.in);
		System.out.print("Please input a main String!");
		String S = in.nextLine();
		System.out.println();
		System.out.print("Please input a pattern!");
		String T = in.nextLine();
		System.out.println("position: "+k.Kmp(S, T));
		in.close();
	}
}

运行结果如下：

数据结构与算法 -- 字符串匹配 KMP算法
字符串匹配
KMP算法 原理
next 数组的推导
KMP 算法代码实现
KMP 算法优化
KMP 算法优化实现

字符串匹配

题目：
给一个仅包含小写字母的字符串主串 S = abcacabdc，模式串 T = abd，请查找出模式串在主中第一次出现的位置；

提示：主串和模式串均为小写字母

KMP算法 原理
对于这道算法题的解法，之前结束了BF算法和RK算法，BF算法是最好理解的，依次对比模式串和主串的各个字符，直到完全匹配，而RK算法解题，是将主串依次拆分为n个模式串长度的子串，并对其通过哈希算法换算成哈希值，进行比较。
而在利用BF算法解题时，会出现下面的情况：
假设主串S = abcababca，模式串T = abcabx，则会出现下面的比较


当比较到最后一个字符X时，不相等，则平移。

当进行到下面的比较时

发现前面两个对a 和b的比较是多余。
因此，可以定义一个数组next，数组的长度为模式串的长度，数组中来存储在进行匹配时，模式串标记j回溯的位置。如下图，直接从j = 3的位置开始比较。

而这就是KMP算法的原理。KMP算法主要是对模式串进行分析处理，依次找出模式串中相同的字符，当有相同字符的时候，j的回溯位置。而next数组的推导是KMP算法的关键。
next 数组的推导


第一种情况，模式串的字符都不相同时
假如：模式串T = abcdex，
当 j = 1 时，next[1] = 0（第一个字符匹配失败，回溯到开始的位置）
当 j = 2 时，匹配字符'b'，此时 1 到 j - 1 的范围内只有'a'，没有相同的字符，匹配失败时，需要从头
            开始即重新匹配'a'，next[2] = 1
当 j = 3 时，匹配字符'c'，此时 1 到 j - 1 的范围内只有'ab'，没有相同的字符，匹配失败时，需要从头
            开始即重新匹配'a'，next[3] = 1
依次类推...
next[4] = 1  next[5] = 1 next[6] = 1






第二种情况，模式串有相等的字符时
假如：模式串T = abcabx
当 j = 1 时，next[1] = 0（第一个字符匹配失败，回溯到开始的位置）
当 j = 2 时，此时 1 到 j - 1 的范围内只有'a'，没有相同的字符，匹配失败时，需要从头
            开始即重新匹配'a'，next[2] = 1
当 j = 3 时，此时 1 到 j - 1 的范围内只有'ab'，没有相同的字符，匹配失败时，需要从头
            开始即重新匹配'a'，next[3] = 1
当 j = 4 时，此时 1 到 j - 1 的范围内只有'abc'，没有相同的字符，匹配失败时，需要从头
            开始即重新匹配'a'，next[4] = 1
当 j = 5 时，此时 1 到 j - 1 的范围内只有'abca'，显然前缀字符'a'与后缀字符'a'相等，匹配
            失败时，可以从字符'b'开始，（P1 - Pk-1 = Pj-k+1 ... Pj-1，得到P1 = P4），
            因此推出 k = 2，因此 next[5] = 2
当 j = 6 时，此时 1 到 j - 1 的范围内只有'abcab'，显然前缀字符'ab'与后缀字符'ab'相等，匹配
            失败时，可以从字符'c'开始，（P1 - Pk-1 = Pj-k+1 ... Pj-1，得到[P1，P2] = [P4, P5]），
            因此推出 k = 3，因此 next[5] = 3



经验： 如果前后缀一个字符相等，K = 2，两个字符相等，K = 3，n个字符相等，K = n + 1



next 数组 回溯理解
假设主串 S = abcababca，模式串T = abcabx，i为T的开始下标，从i = 0开始，j为T结束的下标，从j = 1开始。


i = 0， j = 1
 1.默认 next[1] = 0
 2.i = 0，j = 1，j < T.length，j 从 1-length 开始遍历字符串，
 3.当 i=0 时，表示模式串 T 中【i，j】范围内没有找到相同的字符，所以 i 要回溯到 1 的位置，
 表示 next[j] = i,即next[1] = 0；
 4.或者 T[i] = T[j]，表示找到相等的字符的位置，next[j] = i
 5.不满足以上两个条件，将 i 回溯到 next[i] 的位置。
 
 判断T[i] != T[j]，但是 i = 0，表示【0，1】，这个范围【a】，只能从 1 的位置开始，
 扩大查找相同字符的范围
 所以 i++，j++，i = 1, j = 2，更新 next[j] = i，即：next[2] = 1



i = 1， j = 2
 比较【1，2】范围内是否有相同的字符，
 
 判断T[1] != T[2]（a != b），所以 i 要回溯，i = next[i] = next[1] = 0
 此时，i = 0, j = 2



i = 0， j = 2
 比较【0，2】范围内是否有相同的字符，
 i = 0，又要重头开始比较，扩大查找相同字符的范围，i++，j++,
 i = 1，j = 3
 更新 next[j] = i，即：next[3] = 1



i = 1， j = 3
 比较【1，3】范围内是否有相同的字符，
 
 判断T[1] != T[3]（a != c），所以 i 要回溯，i = next[i] = next[1] = 0
 此时，i = 0, j = 3



i = 0, j = 3
  比较【0，3】范围内是否有相同的字符，没有相同的字符
  i = 0，又要重头开始比较，扩大查找相同字符的范围，i++，j++,
  i = 1，j = 4
  更新 next[j] = i，即：next[4] = 1



i = 1，j = 4
  比较【1，4】范围内是否有相同的字符，
  判断T[1] = T[4]（a = a），扩大查找范围，是否有更长的相同字符
  i++，j++, i = 2, j = 5
  更新 next[j] = i，即：next[5] = 2



i = 2, j = 5
  比较【2，5】范围内是否有相同的字符，
  判断T[2] = T[5]（b = b），扩大查找范围，是否有更长的相同字符
  i++，j++, i = 3, j = 6
  更新 next[j] = i，即：next[6] = 3
  
  j = 6时，模式串 T 已经处理查找完毕





总结：
 在求解 next 数组的4中情况
 1. 默认 next[1] = 0
 2. 当 i= 0，表示当前的比较应该从头开始，则i++，j++，next[j] = i
 3. 当 T[i] = T[j]，表示两个字符相等，则i++，j++，next[j] = i
 4. 当 T[i] != T[j]，表示两个字符不相等，则将 i 回退到合理的位置，则 i = next[i]


next 数组求解 代码

// T 为模式串，T[0]位置存储T的长度
void get_next(String T,int *next){
    int i,j;
    j = 1;
    i = 0;
    next[1] = 0;
    //abcdex
    //遍历T模式串, 此时T[0]为模式串T的长度;
    //printf("length = %d\n",T[0]);
    while (j < T[0]) {
        //printf("i = %d j = %d\n",i,j);
        if(i ==0 || T[i] == T[j]){
            //T[i] 表示后缀的单个字符;
            //T[j] 表示前缀的单个字符;
            ++i;
            ++j;
            next[j] = i;
            //printf("next[%d]=%d\n",j,next[j]);
        }else
        {
            //如果字符不相同,则i值回溯;
            i = next[i];
        }
    }
}


KMP 算法代码实现
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;    /* ElemType类型根据实际情况而定，这里假设为int */
typedef char String[MAXSIZE+1]; /*  0号单元存放串的长度 */

//----字符串相关操作---
/* 生成一个其值等于chars的串T */
Status StrAssign(String T,char *chars)
{
    int i;
    if(strlen(chars)>MAXSIZE)
        return ERROR;
    else
    {
        T[0]=strlen(chars);
        for(i=1;i<=T[0];i++)
            T[i]=*(chars+i-1);
        return OK;
    }
}

Status ClearString(String S)
{
    S[0]=0;/*  令串长为零 */
    return OK;
}

/*  输出字符串T。 */
void StrPrint(String T)
{
    int i;
    for(i=1;i<=T[0];i++)
        printf("%c",T[i]);
    printf("\n");
}

/* 返回串的元素个数 */
int StrLength(String S)
{
    return S[0];
}

//----KMP 模式匹配算法---
//1.通过计算返回子串T的next数组;
//注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
void get_next(String T,int *next){
    int i,j;
    j = 1;
    i = 0;
    next[1] = 0;
    //abcdex
    //遍历T模式串, 此时T[0]为模式串T的长度;
    //printf("length = %d\n",T[0]);
    while (j < T[0]) {
        //printf("i = %d j = %d\n",i,j);
        if(i ==0 || T[i] == T[j]){
            //T[i] 表示后缀的单个字符;
            //T[j] 表示前缀的单个字符;
            ++i;
            ++j;
            next[j] = i;
            //printf("next[%d]=%d\n",j,next[j]);
        }else
        {
            //如果字符不相同,则i值回溯;
            i = next[i];
        }
    }
}

//输出Next数组值
void NextPrint(int next[],int length)
{
    int i;
    for(i=1;i<=length;i++)
        printf("%d",next[i]);
    printf("\n");
}

int count = 0;
//KMP 匹配算法(1)
//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP(String S,String T,int pos){
    
    //i 是主串当前位置的下标准,j是模式串当前位置的下标准
    int i = pos;
    int j = 1;
    
    //定义一个空的next数组;
    int next[MAXSIZE];
    
    //对T串进行分析,得到next数组;
    get_next(T, next);
    count = 0;
    //注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
    //若i小于S长度并且j小于T的长度是循环继续;
    while (i <= S[0] && j <= T[0]) {
        
        //如果两字母相等则继续,并且j++,i++
        if(j == 0 || S[i] == T[j]){
            i++;
            j++;
        }else{
            //如果不匹配时,j回退到合适的位置,i值不变;
            j = next[j];
        }
    }
    
    if (j > T[0]) {
        return i-T[0];
    }else{
        return -1;
    }
    
}

    //KMP算法调用
    StrAssign(s1,"abcababca");
    printf("主串为: ");
    StrPrint(s1);
    StrAssign(s2,"abcdex");
    printf("子串为: ");
    StrPrint(s2);
    Status = Index_KMP(s1,s2,1);
    printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);


KMP 算法优化
假设主串S = aaaabcde，模式串T = aaaaax，在对 next数组求解，得到：
next = [0, 1, 2, 3, 4, 5]，在匹配的过程中，会出现下面情况：

依次字符匹配，当匹配到主串 i=5, 模式串 j=5 时， b != a
则，将 j 回溯到 j = next[j] = 4 的位置
此时依然是 b != a，继续回溯，直到 j = 0
这样前面的几次回溯匹配是没有必要的

所以，我们可以对其进行优化，可以复用前面重复字符的next值，在回溯是时候直接回溯到正确的位置。减少不必要的匹配过程。例如下面的示例：
假设 模式串T = ababaaaba，在求解 nextVal 数组时：

当 j = 1，nextVal[1] = 0
当 j = 2，第二个字符'b'，第一个字符'a'，不相等，nextVal[2] = next[2] = 1
当 j = 3，第三个字符'a'，第一个字符'a'，相等，nextVal[3] = nextVal[1] = 0
当 j = 4，第四个字符'b'，其 next = 2，与第二个字符'b'，相等，nextVal[4] = nextVal[2] = 1
当 j = 5，第五个字符'a'，其 next = 3，与第三个字符'a'，相等，nextVal[5] = nextVal[3] = 0
当 j = 6，第六个字符'a'，其 next = 4，与第四个字符'b'，不相等，nextVal[6] = next[6] = 4

当 j = 7，其 next = 2，与第二个字符'b'，不相等，nextVal[7] = next[2] = 2

当 j = 8，其 next = 2，与第二个字符'b'，相等，nextVal[8] = nextVal[2] = 1

当 j = 9，其 next = 3，与第二个字符'a'，相等，nextVal[9] = nextVal[3] = 0



总结：
在求解 nextVal 数组时:
1. 默认nextVal【0】= 0
2. T【i】= T【j】，且++i, ++j 后，T【i】依旧等于 T【j】，则 nextVal【i】 = nextVal【j】
3. i=0，表示从头开始，i++，j++ 后，T【i】!= T【j】，则 nextVal = j
4. T【i】= T【j】，且++i, ++j 后，T【i】!= T【j，则 nextVal = j
5. T【i】!= T【j】，则将 i 退回到合理的位置， i = nextVal【i】

KMP 算法优化实现
void get_nextVal(String T,int *nextVal){
    int i,j;
    j = 1;
    i = 0;
    nextVal[1] = 0;
    while (j < T[0]) {
        if (i == 0 || T[i] == T[j]) {
            ++j;
            ++i;
            //如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
            if(T[i] != T[j])
                nextVal[j] = i;
            else
            //如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置
                nextVal[j] = nextVal[i];
        }else{
            i = nextVal[i];
        }
    }
}

本文始发于个人公众号：TechFlow，原创不易，求个关注


今天是算法数据结构专题的第29篇文章，我们来聊一个新的字符串匹配算法——KMP。
KMP这个名字不是视频播放器，更不是看毛片，它其实是由Knuth、Morris、Pratt这三个大牛名字的合称。老外很喜欢用人名来命名算法或者是定理，数学里就有一堆，什么高斯定理、欧拉函数什么的。但是中国人更倾向于从表意上来给一个概念命名，比如勾股定理、同余定理等等。之前觉得用人名命名很洋气，作者可以青史留名，后来想想这也是英文表意能力不足，很难用表意的方式起名的体现。
扯远了，我们回到正题。


应用场景


在计算机领域当中字符串匹配其实是一个非常常见的问题，我们使用它的场景也多到不可计数。比如在一个已经打开的页面当中搜索关键词，再比如说git里面的代码变动的记录，以及论文的查重等等。在这些问题当中有些情况可能还好，比如说我们搜索一个关键词，因为关键词并不长，我们暴力枚举也不会特别耗时。但是在有些问题当中明显暴力匹配是无法胜任的，比如论文查重。一篇论文动辄上千词，要和库中的上万篇文章进行查重扫描，这当中的工作量可想而知。如果是暴力枚举算法那查重显然会查到天荒地老。
所以早期的时候字符串匹配是一个难题，既然是难题那么显然就会有很多人来研究，也因此出了很多成果，很多大牛发表了字符串匹配的算法，其中KMP算法由于效率很高、实现复杂度低被应用得最广。到这里，我们就知道KMP算法是用来字符串匹配的。
比方说我们有两个字符串，A串是：I hate learning English. B串是hate learning，很明显B串是A串的字符串。如果我们暴力枚举来判断的话，我们需要遍历A串当中的每一个起始位置是否能够完成匹配，那么复杂度显然是$O(mn)$。通过KMP算法，我们可以在$O(n)$的时间内做到这点。
著名的大佬matrix67在KMP算法的介绍博客当中有一句著名的骚话，当你有一个喜欢的MM，你可以委婉地问她：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？”


Next数组


KMP算法的核心精髓只有一个就是Next数组，但是这个概念并不太容易理解，很多人学KMP放弃就是折戟在了Next这个数组上。
我们先把Next数组是怎么来的放在一边，先来看下Next数组是用来干嘛的，它起作用的原理是什么，最后再来讨论Next数组怎么来的问题。根据我的理解，Next数组其实就是一个中途开始的机会，也就是当我们在枚举匹配的时候，发现了不匹配的情况，我们不是从头开始，而是从一个最大可能的中间结果开始。
我们来看个例子：

上图中上面的是A串，下面的是B串，我们在匹配的过程当中发现B串的前面几位都匹配上了，而在最后一位匹配失败。按照常规的做法，我们应该是移动到下一个位置从头开始匹配。但是这是非常浪费的，因为我们观察下可以发现失败位置的ABC和B串开头的ABC是可以构成匹配的。

我们之前失败的时候判断的是以C结尾的ABCDABC和B串的匹配，在这一次匹配失败之后，我们可以继续尝试匹配其他以C结尾的前缀串，比如ABC。这样我们就可以从中间状态开始，而节省了许多次不必要的枚举。但问题就来了，这个中间结果是怎么来的呢，我们怎么知道当下失败了上一个可行的中间结果是哪一个？
对，没有错，前面说到的Next数组就是用来存储中间结果的。所以Next可以理解成下一次机会的意思，这样就好理解了。由于我们是在A串当中寻找B串，所以这个Next数组应该是针对B的，记录B中每一个位置如果匹配失败，它的前面一个可行的中间状态是哪一个。

我们先写出来B的Next数组，等会再去研究它是怎么得到的。为了简化编码，我们假设字符串是从1位置开始的，所以我们在0的位置添加一个$符号作为占位符。对于大部分情况都是没有重来的机会的，失败了直接归零。而其中的A和B两个位置是有重来机会的，因为B的前缀当中出现了A和AB。所以如果在匹配ABD的时候失败了，我们还可以从AB处再次开始尝试匹配ABC。


算法原理


我们想象一根指针指向了B数组当中接下来要匹配的位置，如果匹配失败了，它就会跳转到Next数组当中记录的位置去，匹配成功了我们就向后移动一位。在有了Next数组之后，我们写出代码来真的很容易了：
def kmp(var_str, template_str):
    # var_str即A串
    # template_str模式串即B串
    # 我们在两个字符串前加上了占位符
    var_str = '$' + var_str
    template_str = '$' + template_str
    next = generate_next(template_str)
    n, m = len(var_str), len(template_str)
    # head指向要匹配的位置的前一位
    head = 0
    for i in range(1, n):
        # 由于next数组很长，可能失败多次
        # 直到head+1的位置能匹配上或者head等于0
        while head > 0 and template_str[head+1] != var_str[i]:
            head = next[head]
        
        # 匹配上了则head变长一位
        if template_str[head+1] == var_str[i]:
            head += 1
        
        # 如果head长度等于B串了，则表示匹配成功
        if head == m - 1:
            return True
    
    return False

对于A串中的每一个位置来说，我们都在B串当中遍历了每一个有可能构成匹配的前缀。所以说这个算法是可行的，一定可以获得解。另外一个问题是复杂度的问题，为什么我们用了两重循环，但仍然是$O(n)$的算法呢？
其实很简单，因为while循环只会让head减小，而不会让head增加。head增加是在for循环里执行的，也就是说head最多增加n次。那么对应的while循环也就最多执行n次，因为head是非负的。所以while循环在整个for循环执行的过程当中最多执行了n次，整体执行的次数仍然是$O(n)$级别的而不是$n^2$级，当然是线性的算法。


求解Next


到这里，问题只剩下了一个，就是这个Next怎么来呢？
其实我们在之前讲Next数组的使用的时候已经泄露天机了，我们再来看下上图，不知道大家能感觉到什么。

后面一个A的Next值是1，也就是第一个A的下标，后面一个B的Next值是2，也就是第一个B的下标。换句话说第二个A能够和位置1的A匹配，后面的AB能和前缀的AB匹配。也就是说Next数组其实就是B数组自己和自己匹配的结果，我们在一开始的时候将整个Next数组全部置为0，然后依次递推迭代出所有的Next的值。
我们在求解Next[i]的时候我们可以利用上Next[i-1]的值，因为Next[i-1]存储的是能够与B[i-1]匹配的前缀的结尾位置。如果B[Next[i-1]+1]等于B[i]，那么说明Next[i] = Next[i-1] + 1。如果不等的话，我们可以用while循环来寻找能够匹配上的前缀。也就是说这是一个递推的过程，不过要注意一点我们计算Next数组要从2开始，因为对于1来说，Next[1]一定等于0。
def generate_next(var_str):
    n = len(var_str)
    next = [0 for _ in range(n)]
    for i in range(2, n):
        # 用next[i-1]作为开始寻找能够匹配上的最长next[i]
        head = next[i-1]
        while head > 0 and var_str[head+1] != var_str[i]:
            head = next[head]
		
        # 如果匹配上了，head+1
        if var_str[head+1] == var_str[i]:
            head = head + 1
        # 记录下来
        next[i] = head
    return next




总结


到这里，我们关于KMP算法的介绍就结束了，不知道大家看完之后感受如何，是不是有点蒙圈呢？
其实蒙圈是正常的，我第一次学的时候足足看了好几遍才算是看明白。这毕竟是一个比较巧妙的算法，想要通过阅读一篇文章就完全学会还是比较困难的，最好的还是亲自动手实现一下试试。KMP算法我最大的感受就是如果你把整个算法的逻辑都串起来了，那么即是自己从头到尾推导一遍难度也不是很大（我就在面试当中推导过一次）。如果你没能把逻辑串起来，那么觉得难理解看不懂是正常的，你可能需要再读一遍或者是寻找一些其他的资料查漏补缺。
今天的文章到这里就结束了，如果喜欢本文的话，请来一波素质三连，给我一点支持吧（关注、转发、点赞）。