2.串的模式匹配

简单的模式匹配

👉视频讲解-4.2.1_朴素模式匹配算法

即暴力算法，相当于前面的Index(S,T)定位操作函数

image.png

使用字符串的基本操作

image.png

直接使用下标

image.png

提示

由于i和j是一起移动的，故i-j可以让i的指针指向开始匹配的前一个位置，例如上图中的i-j=6-6=0,然后再加2，即可让i指向开始匹配的下一个位置

image.png

最坏的情况，每个子串都要对比 $m$个字符，共 $n-m+1$个子串，复杂度为$O((n-m+1)m)=O(nm)$(很多时候，$n\gg m$)

int Index(SString S,SString T){
	int i = 1,j = 1;
	while(i<=S.length && j<= T.length){
		if(S.ch[i]==T.ch[i]){
			++i;
			++j; //匹配上继续比较后续的字符
		}
		else{
			i = i-j+2;
			j = 1; //指针后退重新开始匹配
		}
	}
	if(j>T.length)
		return i-T.length;
	else
		return 0;
}

KMP算法

算法原理

👉视频讲解-4.2.2_1_KMP算法

KMP算法精髓：利用好已经匹配过的模式串的信息

不匹配的字符之前，一定是和模式串一致的

image.png

image.png

该结论对模式串'有通用性，和主串没有关系

image.png

image.png

image.png

朴素算法与 KMP 算法的区别

image.png

求next数组

next数组的含义是next[i]中，i号位置匹配失败，j应该移到哪个位置

👉视频讲解-4.2.2_2求next数组

👉视频讲解-4.2.3_KMP算法的进一步优化

image.png

提示

算法的优化本质上是优化next数组，用优化后的nextval数组进行替换

注意

这里的序号是从1开始的，next[1],next[2]无脑写0、1，但是如果是序号从0开始记得都减1

求nextval数组

核心思想就是看之前当前这个位置模式串是否和将要换成next对应j位置的字符是否一样，一样就没有必要替换成j，而直接替换成next[j]的值，例如下面这道题，正在匹配的b和匹配失败要跳转到2对应的字符也是b，显然还是会匹配失败，所以next[5]不替换成2而是替换成next[2]=1

image.png

image.png

image.png