字符串匹配：KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特—莫里斯—普拉特算法。KMP算法主要分为两个步骤：字符串的自我匹配，目标串和模式串之间的匹配。

KMP.jpg

（一）字符串的自我匹配

所谓字符串的自我匹配，就是看字符串中左右侧相等的最长子串的字符个数。以字符串“12121”为例，左侧的子串为“1”、“12”、“121”或“1212”，注意“12121”不是它本身的子串； 右侧的子串为“1”、“21”、“121”或“2121”。 下面用几个具体的例子来说明： 例1：字符串1212121 从最左边开始算起，1没有子串，匹配的字符个数为0； 12的左右两侧没有相等的子串，匹配的字符个数为0； 121的左右侧有相同的子串1，匹配的字符个数为1； 1212的左右侧有相同的子串12，匹配的字符个数为2； 12121的左右侧有相同的子串1或121，取最长的子串121，所以匹配的字符个数为3； 121212的左右侧有相同的子串12或1212，取最长的子串1212，所以匹配的字符个数为4； 1212121的左右侧有相同的子串1、121或12121，取最长的子串12121，所以匹配的字符个数个数为5 综上所述，字符串1212121的自我匹配结果为0,0,1,2,3,4,5

例2：字符串aaaa 从最左边开始算起，a没有子串，匹配的字符个数为0； aa左右侧相等的最长的子串为a，匹配的字符个数为1； aaa左右侧相等的子串为a或aa，取最长的子串aa，所以匹配的个数为2； aaaa左右侧相等的子串为a或aa或aaa，取最长的子串aaa，所以匹配的字符个数为3。 综上所述，字符串aaaa的自我匹配结果为0,1,2,3

例3：字符串abaabab 从最左边开始算起，a没有子串，匹配的字符个数为0； ab左右侧没有相同的子串，匹配的字符个数为0； aba左右侧有相同的子串a，匹配的字符个数为1； abaa左右侧有相同的子串a，匹配的字符个数为1； abaab左右侧有相同的子串ab，匹配的字符个数为2； abaaba左右侧有相同的子串a或aba，取最长的子串aba，所以匹配的字符个数为3； abaabab左右侧有相同的子串ab，匹配的字符个数为2。 综上所述，字符串abaabac的自我匹配结果为0,0,1,1,2,3,2

从上面的3个例子中，咱们看看能否找到什么规律，这个规律可以使得咱们在字符串的自我匹配过程中不需要每次都从第一个字符开始比较呢？ 以例3中的字符串str[]=”abaabab”为例，咱们将其自我匹配结果放进数组subCnt中，则subCnt[]={0,0,1,1,2,3,2}。

咱们观察到aba的subCnt[2]=1，说明str[0]=str[2]，那么在计算subCnt[3]时，咱们可以先比较一下str[1]和str[3]，如果str[1]等于str[3]的话，那么由原来的str[0]=str[2]咱们可以得知subCnt[3]=subCnt[2]+1=2。若str[1]不等于str[3]，则str[3]再与str[0]比较。

同理，由subCnt[5]=3，可得str[0]==str[3]，str[1]==str[4]，str[2]==str[5]，那么在计算subCnt[6]时，咱们先比较str[6]和str[3]，若二者相等，则str中的前4个（第0，1，2，3）字符与后4个（第3，4，5，6）字符相同，这样可以得到subCnt[6]=subCnt[5]+1=4；若不相等，str[6]应该与谁相比较呢？是str[0]？还是str[1]？或是str[2]？ 由subCnt[5]=3，可知abaaba包含的最大子串的长度为3，这个子串为aba。这时str[6]应该与aba中的最大子串比较。subCnt[3-1]=subCnt[2]=1可推出str[0]==str[2]；二者结合可得str[0] == str[5]。由这个结果，咱们得知str[6]要与str[1]比较，若二者相等则有subCnt[6]=subCnt[2]+1=2。若二者不相等则继续回溯让str[6]与str[0]比较。

这样，我们可以发现这样的规律：str[6]先与str[subCnt[6-1]]（即str[3]）比较，二者不相等后str[6]是与str[subCnt[subCnt[6-1]-1]]（即str[1]）比较。这样就有了如下的递归的规律： 当i=0时，subCnt[0]=0 当i=1时，subCnt[1]=0或1（结果由str[0]是否等于str[1]来定） 当i>=2时，str[i]与str[subCnt[i-1]比较，若相等，则subCnt[i]=subCnt[i-1]+1。若不相等，则str[i]与str[subCnt[subCnt[i-1]-1]比较。若二者相等，则subCnt[i]= subCnt[subCnt[i-1]-1]+1，若不相等，令j=subCnt[subCnt[i-1]-1]，则str[i]继续与str[subCnt[j]-1]比较……如此递归，直到最后str[i]与str[0]比较。

下面给出C语言实现代码：

#include <stdio.h>
#include <string.h>
int* selfMatch(char *str)
{
    int subCnt[100];
    subCnt[0] = 0;
    int i, j, len;
    j = 0;
    len = strlen(str);
    for(i = 1; i < len; i++)
    {
        while (j > 0 && str[j] != str[i])
        {
            j = subCnt[j-1];
        }
        if(str[j] == str[i])
        {
            j++;
        }
        subCnt[i] = j;
    }
    int *pCnt = subCnt;
    printf("字符串自我匹配的结果为:\n");
    for(i = 0; i < len; i++)
    {
        printf("%d ", pCnt[i]);
    }
    return pCnt;
}
int main(int argc, const char * argv[])
{
    char *str = "abaabab";
    selfMatch(str);
    return 0;
}

运行结果：

字符串自我匹配的结果为:
0 0 1 1 2 3 2

（二）目标串和模式串之间的匹配

假定目标串s=”abababadababacb”；模式串p=”ababacb”；p的自我匹配结果subCnt[]={0,0,1,2,3,0,0}。 下面来进行两个字符串之间的比较： i=0,j=0时，s[0]==p[0] i=1,j=1时，s[1]==p[1] i=2,j=2时，s[2]==p[2] i=3,j=3时，s[3]==p[3] i=4,j=4时，s[4]==p[4] i=5,j=5时，s[5]!=p[5] 这样，第一次匹配不相等时，i=5，j=5

这里s[5]不等于p[5]，咱们只能把p串的位置右移，那么移几个位置合适呢？由subCnt[j-1]=subCnt[4]=3，可以得到p[0]==s[2], p[1]==s[3], p[2]==s[4], 这样就可以把p右移，让s[5]和p[3]（即p[subCnt[j-1]]）比较：

i=5,j=3时，s[5]==p[3] i=6,j=4时，s[6]==p[4] i=7,j=5时，s[7]!=p[5] 这里s[7]和p[5]又开始不相等了:

由subCnt[j-1]=subCnt[4]=3，可得p[0]==p[2]==s[4], p[1]==p[3]==s[5], p[2]==p[4]==s[6]，简化得p[0]==s[4], p[1]==s[5], p[2]==s[6], 这样可以把p再右移，让s[7]和p[3]（即p[subCnt[j-1]]）比较：

i=7, j=3时，s[7]!=p[3] 由subCnt[j-1]=subCnt[2]=1可得p[0]==p[2]，又因为p[2]==s[6]，所以p[0]==s[6]，则把p再右移让s[7]与p[1]（即p[subCnt[j-1]]）比较：

i=7, j=1时，s[7]!=p[1] 此时p再右移，将s[7]与p[0]（即p[subCnt[j-1]]）比较：

i=7, j=0时，s[7]!=p[0]，此时j已经达到0的位置，j不能再继续减少，只能依靠i加1（相当于p继续右移）来继续比较:

i=7, j=0时，s[8]==p[0] ……

如此比较下去，结果每相同一次，则j加1。若碰到j=strlen(p)，则说明该时刻s串已经包含了p串。否则s串没有包含p串。

下面给出s串和p串比较的算法：

int match(char *s, char *p)
{
    int *subCnt = selfMatch(p);
    int i = 0, j = 0;
    for(; i < strlen(s); i++)
    {
        while (j > 0 && p[j] != s[i])
        {
            j = subCnt[j-1];
        }
        if(p[j] == s[i])
        {
            j++;
        }
        if(j == strlen(p))
        {
            return i - j + 1;
        }
    }
    return -1;
}

看上面match函数中的算法，是否和selfMatch函数的中的算法神似呢？是的！它们是一样的。实际上selfMatch也相当于两个字符串之间的匹配，只不过模式串是被包含在目标串中的子串罢了。

（三）效率问题

在上面的算法中，设n = strlen(s), m = strlen(p)，注意for循环的内部还有个while循环， 那么该算法的时间复杂度是多少呢？是否是mn？ 假如复杂度是mn的话，那么这个KMP算法相对于BF算法就谈不上改进了。 分析一下这个while循环，实际上它的作用就是让j不断变小，导致p串不断右移。显然，在i=0到i=n-1的整个比较过程中，j最多只能往右挪移n次，所以while循环的平均复杂度最多为1，所以KMP算法是线性的，复杂度是n，而不是mn。这就是KMP算法存在的价值。

（四）完整代码

#include <stdio.h>
#include <string.h>
int* selfMatch(char *str)
{
    int subCnt[100];
    subCnt[0] = 0;
    int i, j, len;
    j = 0;
    len = strlen(str);
    for(i = 1; i < len; i++)
    {
        while (j > 0 && str[j] != str[i])
        {
            j = subCnt[j-1];
        }
        if(str[j] == str[i])
        {
            j++;
        }
        subCnt[i] = j;
    }
    int *pCnt = subCnt;
    printf("字符串自我匹配的结果为:\n");
    for(i = 0; i < len; i++)
    {
        printf("%d ", pCnt[i]);
    }
    return pCnt;
}
int match(char *s, char *p)
{
    int *subCnt = selfMatch(p);
    int i = 0, j = 0;
    for(; i < strlen(s); i++)
    {
        while (j > 0 && p[j] != s[i])
        {
            j = subCnt[j-1];
        }
        if(p[j] == s[i])
        {
            j++;
        }
        if(j == strlen(p))
        {
            return i - j + 1;
        }
    }
    return -1;
}
int main(int argc, const char * argv[])
{
    char *szSource = "abababadababacb";
    char *szSub = "ababacb";
    int pos = match(szSource, szSub);
    if(-1 != pos)
    {
        printf("\n目标串包含模式串,起始位置是：%d", pos);
    }
    return 0;
}

运行结果：

字符串自我匹配的结果为：
0 0 1 2 3 0 0
目标串包含模式串,起始位置是：8