字符不等时同时向前回溯了两个指针一个是主串的指针一个是子串的指针。而KMP算法的基本思路是在不回溯主串的指针而只回溯子串的指针的情况下完成模式匹配这样就省去了回溯主串指针进行比较的一部分时间。
KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。
还是相同的例子在S”abcabcabdabba”中查找T”abcabd”如果使用KMP匹配算法当第一次搜索到S6和T6不等后S下标不是回溯到2T下标也不是回溯到开始而是根据T中T6’d’的模式函数值
ext63为什么后面讲直接比较S6和T3是否相等因为相等S和T的下标同时增加因为又相等S和T的下标又同时增加。。。最终在S中找到了T。如图
ext63含义其实这个3表示T6’d’的前面有2个字符和开始的两个字符相同”。请看图因为S5T5S4T4根据
ext63有T4T1T5T2所以S4T1S5T2两对相当于间接比较过了因此接下来比较S6和T3是否相等。
f有人可能会问S4和T1S5和T2是根据
ext63间接比较相等那S2和T1S3和T1之间又是怎么跳过可以不比较呢因为S1T1S2T2S3T3而T1T2T2T3S1S2S2S3所以S2T1S3T1还是从理论上间接比较了。
5怎么求串的模式值
ext
定义
0如果j1
extjMaxk1kj且p1pk1pjk1pj1
1其它情况
1
ext10意义任何串的第一个字符的模式值规定为0。
2
extjk意义模式串T中下标为j的字符如果j的前面k1个字符与开头
的k1个字符相等
即T1T2……Tk1Tjk1Tjk2…Tj1
3
extj1其他情况。
例1求T“abcac”的模式函数的值。
f例2求T”ababcaabc”的模式函数的值。
例3求T”abCabCad”的模式函数的值。
课后题求T”ababcabababc”的模式函数的值。
6
ext
不足与改进
KMP的改进算法主要是针对求NEXT数组的算法思想进行的改进。
数组的效率引入了NEXTVAL数组即NEXT的改进值。NEXTVAL避
比如“abcdabce”模式串中NEXTNEXTVAL值为01110114。当比较到T7C不成功时原NEXT
T3也是C与T7相同所以可以直接跟T1比较。
举例若T“abcab”的模式函数的值
f标
Tabcab
01112
ex
t
若S“abcadcabcab”
f
ext
改进为
extval
如果TjTkk
extj否则k
extk
12345
下
标
Tabcab
01101
ex
t
练习求T”AAAAAAAAAAB”的模式函数值并用后面的求模式函数值函数验证。
7
ext
意义
设在字符串S中查找模式串T若SmT
那么取T
的模式函数值
ext
1、
ext
0表示Sm和T1间接比较过了不相等下一次比较Sm1和
T1r