磨人的KMP算法

之所以说KMP磨人是因为，他真的不怎么好懂，就算懂了，也不怎么好写0.0也有可能是我太菜了

KMP算法就是为了应对暴力匹配字符串带来的庞大的消耗，总的来说就是在匹配字符串的过程中如果发生匹配失败，不采用暴力匹配的方法直接从当前字符串的下一个位置开始匹配，而是最大程度的把匹配串向右移动尽可能多的字符。当然这里的移动并不是随便移动，而是根据一个移动表格（next数组）来进行移动

暴力匹配的思想就是逐个匹配，但是这是KMP怎么会这么low，当然对于下面这个字符串，刚开始可能和暴力匹配差不多

BBC ABCDAB ABCDABCDABDE

ABCDABD

依旧不相等，继续整体后移

BBC ABCDAB ABCDABCDABDE

#ABCDABD

整体移动到下面位置时，匹配成功一个字符

BBC ABCDAB ABCDABCDABDE

### ABCDABD

然后匹配一次对后面的字符进行匹配

BBC ABCDAB ABCDABCDABDE

### ABCDABD

到这个位置匹配失败，按照暴力匹配的方法应该将匹配串的头和目标串的第6个字符进行比较，但是根据KMP的思想，应该在出现错误的基础上，最大限度的右移匹配串

BBC ABCDAB ABCDABCDABDE

### ABCDABD

然后根据之前构造好的Next表（后续会说明Next表的原理），在D位置匹配失败，然后匹配成功的最后一个字符是B，B对应的Next数组值为2，这个时候我们就应该将字符串后移：（已经匹配的字符个数-部分匹配值）个字符

ABCDABD

000012

因为已经匹配的字符数是6，部分匹配值是2，所以得出字符串向后移动4个单位

BBC ABCDAB ABCDABCDABDE

### ####ABCDABD

然后按照常规的匹配的规则继续匹配，直到出现下图的情况。再按照KMP的处理方法，尽可能的后移匹配串，知道匹配成

BBC ABCDAB ABCDABCDABDE

### ####ABCDABD

到这里都好懂，然后就开始想这个Next数组是怎么求出来的？然后我就懵逼在Next数组上

说到这了都，问题就演变成了如何求Next数组的部分匹配值了。网上其他的博客上还引入了前缀和后缀的概念，但是我认为没有什么必要。所谓的部分匹配值就是，从头开始对匹配串进行重复查找，简单的来说A B C D A B D，1-4的部分匹配值为0，但是5-6出现了重复组A B，第7位虽然也在前面出现，但是组A B D没有在前面出现，所以D位置的部分匹配值为0

OK，原理大概就是这样，剩下的一个问题就是代码了

其实整体很难解决的就是一个Next数组的构造和KMP的主程序

根据上面的原理实际上Next数组就很好实现了

void setNext(const char P[],int next[])
{
    int q,k;//q:模版字符串下标；k:最大前后缀长度
    int m = strlen(P);
    next[0] = 0;
    for (q = 1,k = 0; q < m; ++q)
    {
        while(k > 0 && P[q] != P[k])
            k = next[k-1];        
        if (P[q] == P[k])
        {
            k++;
        }
        next[q] = k;
    }
}

既然有了Next数组，那就可以很愉快的写KMP函数了

int kmp(const char T[],const char P[],int next[])
{
    int n,m;
    int i,q;
    n = strlen(T);
    m = strlen(P);
    setNext(P,next);
    for (i = 0,q = 0; i < n; ++i)
    {
        while(q > 0 && P[q] != T[i])
            q = next[q-1];
        if (P[q] == T[i])
        {
            q++;
        }
        if (q == m)
        {
            printf("匹配串开始的位置是:%d\n",(i-m+1));
        }
    }    
}

这么看的话磨人的KMP算法其实也不是很难