数据结构-基于Python语言（微课版） 课件T9-串(模式匹配)

模式匹配第四章：串

主讲：周翔朴素的模式匹配算法（BF算法）朴素的模式匹配算法思路：从主串s的第一个字符开始与t的第一个字符作比较；如果相等，继续逐个比较后续的字符；如果不相等，使主串的第二个字符与t的第一个字符比较：如果相等，继续逐个比较后续的字符；如果不相等，使主串的第三个字符与t的第一个字符比较：………以此类推，直到主串s的一个连续子串序列与模式t相等，返回子串序列在s串中的位置；否则匹配不成功，返回-1。朴素的模式匹配算法（BF算法）朴素的模式匹配算法思路：abecdecd主串s子串t从主串s的第一个字符开始与t的第一个字符作比较不相等从主串s的第二个字符开始与t的第一个字符作比较不相等从主串s的第三个字符开始与t的第一个字符作比较相等继续比较后面的字符相等继续比较后面的字符相等匹配成功朴素的模式匹配算法（BF算法）朴素的模式匹配算法（BF算法）KMP算法KMP算法（无回溯的模式匹配）：KMP算法的主要思想就是利用已得到的部分匹配信息来进行后面的匹配过程，消除主串的回溯，从而提高匹配的效率。子串t主串scabxabeahycabdabKMP算法由匹配结果可以得出如下信息：t[0]=s[0]；t[1]=s[1]；t[0]!=t[1]==>t[0]!=s[1]；t[0]=s[0]；t[2]=s[2]；t[0]!=t[2]==>t[0]!=s[2]；t[0]=s[0]；t[3]=s[3]；t[0]=t[3]==>t[0]=s[3]；

t[1]=s[1]；t[4]=s[4]；t[1]=t[4]==>t[1]=s[4]；子串t主串scabxabeahycabdab因此下一次比较就比对s[5]与t[2]是否相等。这样就省去了主串的回溯KMP算法KMP算法（无回溯的模式匹配）：对于t的每个字符t[j](0<=j<=m-1)，若存在一个整数k(k<j)，使得模式t中k所指字符前的k个字符(t0t1…tk-1)依次与tj的前面k个字符(tj-ktj-k+1…tj-1)相同，并与主串s中i所指字符之前的k个字符相同，那么利用这种匹配信息就可以避免不必要的回溯。在匹配之前，用一个数组next来存放模式串t中字符的匹配信息，通过分析t中的字符，得出匹配完当前字符后，下一次要匹配哪一个字符，将该字符信息存入next数组。存入next数组的这个值也称为模式值、next值。KMP算法KMP算法（无回溯的模式匹配）：next值的推导规则如下所示：（1）next[0]=-1：任何串中第一个字符的模式值规定为-1；（2）next[j]=1：模式串t中下标为j的字符与首字符相同，且j之前的1-k个字符与开头的1-k个字符不等（或者相等但t[k]=t[j]）（1<=k<j）；（3）next[j]=k：如果模式串t中下标为j的字符之前k个字符与t开头的k个字符相等，且t[j]!=t[k]（1<=k<j），则next[j]=k；（4）next[j]=0：除（1）、（2）、（3）之外的其他情况next[j]都为0；KMP算法abcabd-100012bfbfbfkmpbf-10012340001KMP算法——分析总结本章主要讲解了串的相关知识，包括串的概念、串的存储结构、以及串常用的模