m数据结构 day7 串（二）KMP模式匹配算法

港控/mmm° 2023-03-13 05:28 4阅读 0赞

### 文章目录 ###

*  KMP算法
 *   *  KNP算法的灵魂：主串指针i不回溯，模式串指针j的回溯量取决于j当前指向的字符之前的串（模式串的子串）的前后缀的相似度
     *  串的next数组：简单，next\[i\]的值减1 就是 模式串j从1到i-1的子串的最长公共前后缀的长度
     *  KMP的代码
     *   *  返回子串T的next数组，难,时间复杂度O(m),m是子串长度
         *  用KMP进行模式匹配，返回模式串在主串中的位置，时间复杂度O(m+n)
     *  和朴素遍历算法的对比：KMP在模式和主串之间存在许多“部分匹配”时优势明显
 *  KMP算法的改进:改进next数组为nextval，减少j回溯时的多余判断
 *   *  nextval数组值推导
     *   *  推导公式
         *  原理
     *  例子
     *  计算nextval数组的函数代码

# KMP算法 #

KMP，是三个科学家的名字连在一起，他们三个发表了这个算法，即  
![在这里插入图片描述][20200507120414631.png]

![在这里插入图片描述][20200507120440945.png]

## KNP算法的灵魂：主串指针i不回溯，模式串指针j的回溯量取决于j当前指向的字符之前的串（模式串的子串）的前后缀的相似度 ##

导致朴素模式匹配算法效率低下的原因就是主串指针要不停的回溯。KMP算法的核心和灵魂就是找到了办法使得i可以不回溯，永远向主串的前方前进。但是模式串的指针还是要回溯的，但是不需要直接回溯到模式串的开头，而是根据需要来回溯，于是回溯步数也会减少。总之，不必要的重复判断次数都被精简掉了，因此KMP的效率很高。

模式匹配的过程中主串和模式串都有一个指针，主串的指针用i表示，模式串的指针用j表示，如图（这里i,j都从1开始的）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]

判断过程如下，首先i,j从1增长到6，出现不匹配，此时i不动，看模式串的第j个字符前面的串，abcab，其最长公共前后缀是ab(下面说next数组会说到最长公共前后缀的含义)，所以我们把模式串直接往后移动3步使得最长公共前后缀前后缀重合，并让j回溯到j=3，其实j相对于主串的位置没变，只是模式串动了所以j的值就自然减小（回溯）了。

于是从j=3,i=6开始，i,j都增加，逐个匹配，直到i=9,j=6，再次不匹配，但是此时i已经到了主串的最后了，无法再前进，所以这次匹配以失败告终，主串中没有这个模式串。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70_pic_center]

## 串的next数组：简单，next\[i\]的值减1 就是 模式串j从1到i-1的子串的最长公共前后缀的长度 ##

串的next数组用于在代码中确定模式串j从1到i-1的子串的最长公共前后缀的长度，以确定指针j的回溯步数和模式串的移动步数

定义如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]  
j是模式串T的字符索引，从1到T的长度（这里没从0开始哈，你也可以从0开始，其实本质都一样）.

定义第二行的 P 1 , ⋯   , k − 1 P\_\{1,\\cdots,k-1\} P1,⋯,k−1是j从1到j-1的子串的最长公共前后缀的前缀子串， P j − k + 1 , ⋯   , j − 1 P\_\{j-k+1,\\cdots,j-1\} Pj−k\+1,⋯,j−1是j从1到j-1的子串的最长公共前后缀的后缀子串。二者长度都是k-1.

举几个例子：

1.  例子1  
    ![在这里插入图片描述][20200511134948446.png]

*  j=1,按照next数组定义，next\[1\]自然是0.
 *  j=2，没有满足1<k<j的k,所以是空集。所以是其他情况，next\[2\]=1.
 *  j=3,k=2是唯一满足1<k<j的k， P 1 = P 2 P\_1=P\_2 P1=P2,不满足，所以还是其他情况，next\[3\]=1
 *  j=4，j从1到j-1的子串是abc,没有相等的情况，所以还是其他情况，Next\[4\]=1
 *  后面全部同上，所以全部是1.

其实你会发现，next数组的前两位一定是01，因为定义死死地决定了必须是这样。

1.  例子2  
    ![在这里插入图片描述][20200511135517115.png]

我们用找最长公共前后缀的方式避免用next数组的定义的第二行去逐个枚举k并判断。

*  j=3,j从1到j-1的子串是ab，没有前后公共子串，所以next\[3\]=1
 *  j = 4,同上
 *  j=5,j从1到j-1的子串是abca,第一个字符a和最后一个字符a相等，且没有更长的前后公共子串，所以k=2。（这也是发现的规律，如果最长公共前后缀的长度是n,则k就等于n+1,这样就刚好是满足 P 1 , , , K − 1 = p j − k + 1 , , , j − 1 P\_\{1,,,K-1\}=p\_\{j-k+1,,,j-1\} P1,,,K−1=pj−k\+1,,,j−1的最大的K）,next\[5\]=2
 *  j=6，子串是abcab,最长公共前后缀是ab,所以k=3。 next\[6\]=3

1.  例子3  
    ![在这里插入图片描述][20200511135531420.png]  
    前几个简单就不说了，和上面一样。

*  j = 6,子串是ababa，千万不要以为只有第一个a和最后一个a,误判k=2。当然不误判的好办法就是用next数组定义第二行单个单个枚举k,你就会发现最大的满足条件的K不是2，而是4。 P 123 = P 345 P\_\{123\}=P\_\{345\} P123=P345。其实这种时候，j-k+1=k-1,即j=2k-2,这里6=2\*（4-1）。
 *  j=7,ababaa,这时候最长就是a了。

**找最长公共前后缀的方法是**：先找到j从1到j-1的子串，然后比对第一个字符和最后一个字符，如果不相等，则没有公共子串；如果相等，则继续比对第二位和倒数第二位，如果不相等，则最长公共前后缀的长度就是1，就是第一个字符和最后一个字符·····

1.  例子4

来看个特殊的例子  
![在这里插入图片描述][20200511135543212.png]  
j=8,子串是7个a，aaaaaaa,前缀子串是aaaaaa,后缀子串也是aaaaaa，所以k=7.这里要注意前后子串不可能完全相同（说的是位置），即都为7个a,因为next数组定义中第二行规定了k<j,如果前后子串相同，即j-k+1=1,且j-1=k-1，那就说明j=k。和规定矛盾。所以k一定是小于j的。

## KMP的代码 ##

### 返回子串T的next数组，难,时间复杂度O(m),m是子串长度 ###

这个函数太绕了，如此简洁的代码，实现了如此复杂的功能，我感觉用语言是很不好表述这个代码的功能的，但是代码却这么简洁，我至今还没梳理清楚，真的是考验智商

/*返回子串T的next数组，数组索引从1到T[0]*/
    void get_next(String T, int * next)
    { 
    	int i, j;
    	i = 1;
    	j = 0;
    	next[1] = 0;
    	while (i < T[0])//T[0]表示串T的长度，即不用\0表示字符串结尾，而用长度
    	{ 
    		if (j==0 || T[i]==T[j])//T[i]表示后缀的单个字符，T[j]表示前缀的单个字符
    		{ 
    			++i;
    			++j;
    			next[i] = j;//next[2]一定为1，T[i]==T[j]则把next[i+1]置为j+1（j等于最长公共前缀的长度，即上面推到中的k）
    		}
    		else
    			j = next[j];//若字符不同,即T[i]!=T [j], 则j值回溯.i的值从未回溯，一直在增加
    	}
    }

### 用KMP进行模式匹配，返回模式串在主串中的位置，时间复杂度O(m+n) ###

/*返回模式串T在主串S中第pos个字符之后的位置，如果不存在，则返回0*/
    //1<=pos<=StrLenth(S),T非空
    int Index_KMP(String S, String T, int pos)
    { 
    	int i = pos;
    	int j = 1;
    	int next[255];
    	get_next(T, next);//得到模式串的next数组
    	while (i < S[0] && j < T[0])//S[0]和T[0]存储串的长度
    	{ 
    		if (j==0 || S[i]==T[j])
    		{ 
    			++i;
    			++j;
    		}
    		else
    			j = next[j];//S[i]!=T[j]，则j回溯j-next[j]步，其实是模式串右移了j-next[j]步，回溯到next[j+1]的值表示的位置，注意，i并不回溯，一直前进
    	}
    	if (j > T[0])//匹配到了
    		return i-T[0];//当前i回溯模式串长度的位置就是匹配到的子串的开始位置
    	else //没匹配到
    		return 0;
    }

while循环的时间复杂度是O（n），n是主串长度，因为最多要执行主串长度次嘛。而get\_next的时间复杂度是O(m),m是模式串长度，所以总的KMP的时间复杂度是O(m+n)

## 和朴素遍历算法的对比：KMP在模式和主串之间存在许多“部分匹配”时优势明显 ##

KMP时间复杂度是O(m+n);朴素遍历的时间复杂度是O((n-m+1)\*m)，KMP时间复杂度明显好一些。

# KMP算法的改进:改进next数组为nextval，减少j回溯时的多余判断 #

这是针对某一些主串和模式串发现的，KMP在这类匹配中还是会有很多重复判断，举个例子更加直观地看到：

主串S=“aaaabcde”,模式串T=“aaaaax”,模式串的next数组的每一个位置的值分别是012345。第一次匹配，i=5,j=5时发现不匹配，于是j回溯，j=next\[j\]=4,；可是i=5，j=4还是不匹配，因为j=4位置的字符和j=5的字符一样啊。由于还是不匹配，j只好又回溯，j=3,j=2直到j=0，才能做出有效操作，即i前进一步，i=6，j=1，去判断之前没判断过的。而j=5直到j=1的字符都是a,明显做了5次重复判断，其中4次可以避免掉。

KMP的改进就是基于next数组的这个问题，做了改进。**改进的思路是**：对于T串而言，前5个字符相同，所以为了避免j的无效回溯，next数组中next\[1\]直到next\[5\]可以设置为和next\[0\]相同的数值,这样**一步就直接回溯到j=0处**了。

## nextval数组值推导 ##

### 推导公式 ###

![在这里插入图片描述][2020051212481480.png]  
即，从j=2开始，图中P指的是模式串，之前KMP中，j回溯的代码是j=next\[j\],即j退回为next\[j\],(next\[j\]一定小于j)，这是通过模式串前移j-next\[j\]步实现的。现在，如果P\[j\]和P\[next\[j\]\]是同一个字符，那么就递归回溯（下面会说），j处的nextval值就等于next\[j\]出的nextval值。

### 原理 ###

看了[July老师的博客][July]后，我理解了一点了。但是这两天实在心浮气躁，可能五月天热压力又大，不想特别深入完整看完一个视频或者一篇长文，自己的理解也就不是完全到位，只是知道了皮毛，后面再努力吧。现在先说说现在的理解：

July老师说到了核心，nextval数组按上面的规则来，是为了保证T\[j\]!=T\[next\[j\]\],比如：  
模式串T是abab（next数组是0112）,主串是abxbcedf

i=3,j=3时匹配失败，如图：  
![在这里插入图片描述][20200512132945717.png]  
如果按照之前的KMP，那么j=next\[j\]=next\[3\]=1, j回溯j-next\[j\]步，即2步，（**实际上j的回溯是通过模式串前移两步实现的**）。但是模式串前行两步，让T\[1\]和x匹配，T\[1\]不还是字符a吗？？？如图：  
![在这里插入图片描述][20200512133044739.png]  
那之前a和x匹配失败，现在回溯了得到的还是a,那**必然还是匹配失败**啊！没办法，失败了就继续回溯，j=next\[j\]=next\[1\]=0,由于j=0，所以++i,++j,i=4,j=1,即：

![在这里插入图片描述][20200512132823469.png]

KMP的改进正是抓住了这一点，即如果 T \[ j \] = = T \[ n e x t \[ j \] \] T\[j\]==T\[next\[j\]\] T\[j\]==T\[next\[j\]\],则j回溯后必然还是匹配失败，因为两次匹配的字符完全一样，第一次失败第二次必然还是失败，失败就要继续回溯，所以KMP改进时对于 T \[ j \] = = T \[ n e x t \[ j \] \] T\[j\]==T\[next\[j\]\] T\[j\]==T\[next\[j\]\]的就递归回溯，一次性回溯到不会出现 T \[ j \] = = T \[ n e x t \[ j \] \] T\[j\]==T\[next\[j\]\] T\[j\]==T\[next\[j\]\]的时候：

对上面的例子，还从第一步开始，i=3,j=3匹配失败：  
![在这里插入图片描述][20200512132945717.png]  
由于 T \[ 3 \] = = T \[ n e x t \[ 3 \] \] = = T \[ 1 \] = = a T\[3\]==T\[next\[3\]\]==T\[1\]==a T\[3\]==T\[next\[3\]\]==T\[1\]==a,所以继续回溯，即j=next\[next\[j\]\]=next\[1\]=0,那么回溯步数是j-0=3步，即模式串直接一次前进三步，得到了上面例子的两次回溯后的结果：  
![在这里插入图片描述][20200512132823469.png]

就是这种递归回溯，避免了多于判断，进一步提升了效率，这也是为什么nextval数组的每一个值要那样定义的原因。

## 例子 ##

![在这里插入图片描述][2020051213422459.png]

![在这里插入图片描述][20200512134234484.png]

## 计算nextval数组的函数代码 ##

/*求模式串T的nextval数组，即next数组的修正版*/
    void get_nextval(String T, int * nextval)
    { 
    	int i, j;
    	i = 1;
    	j = 0;//j一直小于等于i
    	nextval[1] = 0;
    	while (i < T[0])//T[0]是模式串长度
    	{ 
    		if (j==0 || T[i]==T[j])
    		{ 
    			++i;
    			++j;
    			if (T[i]!=T[j])
    				nextval[i] = j;//和之前next数组值一样
    			else
    				nextval[i] = nextval[j];//递归回溯
    		}
    		else
    			j = nextval[j];//j的回溯，之前是j = next[j]
    	}
    }

[20200507120414631.png]: /images/20230312/0e73918d96584f668e6891290c56ed4b.png
[20200507120440945.png]: /images/20230312/8fe25aafd550412992f929afa7d50c80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: /images/20230312/5e1eb01620fd4b20ab5945278fa5cf00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70_pic_center]: /images/20230312/09cb94ff4bfa4790884349d269f503c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: /images/20230312/5419a64b80f0465183e40534bb4f0673.png
[20200511134948446.png]: /images/20230312/7fe3a37862104ded9885557e45e73581.png
[20200511135517115.png]: /images/20230312/2ceb0e050735411bb78b05c2c3569188.png
[20200511135531420.png]: /images/20230312/166c065b77924c8b99f896b87dea6fd8.png
[20200511135543212.png]: /images/20230312/9547ff15ef7f4eed81cea1cc64404069.png
[2020051212481480.png]: /images/20230312/943ef33e2cb24d3aae6271de374999a2.png
[July]: https://blog.csdn.net/v_july_v/article/details/7041827
[20200512132945717.png]: /images/20230312/df0e538da88546118c8e8ebe9b8d7703.png
[20200512133044739.png]: /images/20230312/c3b77bc6773c416aa868bb9576663c9f.png
[20200512132823469.png]: /images/20230312/f174d9ef5775451fafce0275245628bc.png
[2020051213422459.png]: /images/20230312/20857cd14d554afc9f777150fde634bf.png
[20200512134234484.png]: /images/20230312/43a00703ead14a00b2c48723d4daab7f.png