字符串的模式匹配(精准匹配)
1.朴素的模式匹配算法
2.字符串的特征向量与KMP模式匹配算法
1.朴素的模式匹配直接贴代码
2.1字符串的的特征向量
例如在目标(target)字符串t中:abcabcabcc中
寻找模式(pattern)字符串p: abcabcc
可见t6与p6不匹配
如果用朴素的匹配思想只需要将模式串一次向右移动一位即可
此时t3-t9与模式串匹配 输出3即可,但是我们去思考一下复杂度
最坏情况就是t9与p6匹配 需要比较多少次呢?观察上面三张图片,每次右移一位就需要比较7次
也就是比较了p.length*(t.length-p.length+1)次 复杂度为O(|T||P|)
这其中有很多不必要的重复操作
第一次比较t6与p6不匹配
观察模式串p自身 p0-p2与p3-p5是一样的都是abc 而第一次不匹配是发生在t6与p6,也就是说第一次比较t0-t5是完全等于p0-p5的
1.模式串p自身p0-p2与p3-p5相等(同为abc)的特性
2.t0-t5 又依次相等与p0-p5
得出p0-p2必然等于t3-t5所以直接比较t6与p3即可
将模式串p直接右移三位。(少了右移一步和右移两步朴素算法当中比较的12次)少了很多重复比较
需要知道的是这是模式串自身的特性,所以我们不再考虑目标串。
在模式P与目标T的匹配过程中,当某次比较出现Pi≠Tj时意味着在此前的匹配历史中有下述匹配的子串满足P(0.....i-1)=T(j-i....j-1)相等,如果P(0....i-2)=P(1....i-1)成立,即表示模式右移一位后,P(0....i-2)与T(j-i+1...j-1)必下相等。所以此时直接比较Pi-1和Tj即可。由此可知,利用之前的比较结果减少了在目标串上的回溯。若P(0....i-2)=P(1....i-1)不成立,则可以继续查看P(0....i-3)与P(2....i-1)是否相等,若相等,则将模式右移两位,因为此时P(0....i-3)与T(j-i+2....j-1)必然相等。依次类推,必然可以找到某个K值,使得P(0....i-k-1)=P(k....i-1)成立,此时把模式右移K位开始下一次匹配,既不会丢失配串,又不会产生目标回溯的情况。 字符串的特征数Ni是递归定义的
1)N0=0,对于i>0的Ni,假定已知前一个字符的特征数N(i-1)=K;
2)如果i>0且Qi=Qk 则Ni=K+1;
3)当Qi≠Qk 且K≠0时,令K=N(K-1),并让(3)循环到条件不满足;
4)当Qi≠Qk,且K=0时,则Ni=0;
给出计算模式串特征向量的算法
KMP模式匹配算法