阅读数:131 评论数:0

字符串的匹配包括蛮力匹配算法，KMP算法，BM算法，Horspool算法，Sunday算法，fastsearch算法，KR算法等等。

本文主要介绍KMP算法和BM算法，它们分别是前缀匹配和后缀匹配的经典算法。所谓前缀匹配是指：模式串和母串的比较从左到右，模式串的移动也是从左到右；所谓后缀匹配是指：模式串和母串的的比较从右到左，模式串的移动从左到右。看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同。

1、KMP

KMP算法中的KMP分别是指三个人名：Knuth、Morris、Pratt，与蛮力匹配算法的区别在于它会动态调整每次模式串的移动距离，而不仅仅是加一，从而加快匹配过程。

设T为母串，P为模式串，模式串的长度为m，则kmp算法的伪代码：

j:=0;
for i:=1 to n 
    while(j>0&&p[j+1]!=T[i]) j:= jump[j];
    if(p[j+1]==T[i])  j:=j+1;
    if(j==m) cout<<"pattern occurs with shift "<<i-m<<endl;

KMP算法中jump数组的构建可以通过归纳法来解决：

（1）首先确定jump[1]=0；

（2）假设jump[j]=k，也就是P[0, j] == P[k-j, k]

（3）如果P[j+1] == P[k+1]，那么jump[j+1] = k+1；

（4）如果P[j+1] != P[k+1]，那就接着比较P[j+1] ?= P[k1+1]，其中（jump[k] = k1）

（5）如果此时P[j+1] == P[k1+1]，则得出：jump[j+1] = K1 +1 = jump[k] +1。

（6）如果P[j+1] != P[K1+1]，继续递归比较P[j+1] 和P[jump[jump[k]]+1]  ….  P[1]；
（7）如果依次比较都不相等，那么jump[j+1] = 0；

jump[1]  = 0;
j = 0;
for (i=2;i<=m;++i)
    while(j>0&&p[j+1]!=p[i]) j=jump[j];
    if(p[j+1] = p[i]) j = j+1;
    jump[i] = j;

KMP算法最差的时间复杂度是O(n)；最好的时间复杂度是O(n/m)。

其实jump数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。例如：

ababaca

jump[1] = 0，

jump[2] = 0，对就串ab的的前缀与后缀的最长相同长度为0

jump[3] = 1, 对应中aba前缀与后缀的最长相同长度为1，相同部分为a

jump[4] = 2, abab=>ab

jump[5] = 3, ababa=>aba

jump[6] = 0, ababac

jump[[7] = 1, ababaca=>a