字符串的模式匹配（精准匹配）

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    

  将模式串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模式匹配算法