KMP 算法入门

今天算是认真学习了一下KMP吧，以前的时候一直觉得KMP非常难理解，现在仔细想想KMP 真的不算是一个非常难的算法，尤其是如果理解了他的原理，那么我们就只会惊叹于，K/M/P 他们思想的伟大了。

现在我就介绍一下KMP吧
首先KMP的作用是在一串字符中，找出所含有的字串的个数

对于一般的暴力匹配算法来说，我们如何要匹配一个字符串，首先我们将待匹配的字符串成为目标串，用于匹配的字符串称为模式串，那么我们只需要从目标串的每一个字符开始枚举，判断是否与模式串匹配即可。此时的复杂度将会是O( )

而KMP就发现，由于每次匹配都是从头开始匹配的，我们匹配了一段之后，又要从刚刚匹配过的第二个字符再重新匹配，显得非常繁琐，那么我们可不可以匹配完一次之后，就能找到下一次匹配我应该从哪里开始呢？
那么我们来观察一下目标串与模式串之间的关系
比如说 ababcabab
如何我的目标串 abab
那么我找到abab 之后，很显然，下一次我肯定不用从b开始找，最好就是从第二个a开始找，那么我们怎么知道第二个a在哪里呢，现在我们可以做一个预处理，对于目标串来说，我们去寻找这个目标串的每个前缀字符串的相同的最长前缀和最长后缀的长度，这句话听起来有点拗口，下面解释一下上面的例子你就知道了
对于ababcabab来说，他的所有前缀字符串包括(“a”,”ab”,”aba”,”abab”,”ababc”,”ababca”,”ababcab”,”ababcaba”,”ababcabab”)
那么比如说从中任选一个 ababcaba 他的相同的最长前缀和最长后缀就是“aba”，此时的长度就是3，为什么要找到这个3呢，我们想象一下，假设有一个模式串，在”ababcaba”的最后一个位置匹配失败了，那么可以想象，前面若干个都是正确的已经匹配好的串，所以，开头一定是aba，那么我们就从第二个aba开始下一轮匹配就好了，下一次匹配的时候只要比较下一个字符是否和第四个字符相同，这样就不会浪费已经匹配完成的情况了。
如果我们用Next[0…8]数组记录每一个字符串相同的最长前缀和最长后缀长度的话
Next[0…8]={-1,0, 0 ,1 ,2, 0 ,1, 2}
现在看一下代码

void GetNext()
{
    int i=0,j=-1;
    Next[0]=-1;
    int len=strlen(str);
    while(i<len)
    {
    if(j==-1||str[i]==str[j]) Next[++i]=++j;
    else j=Next[j];
    }
}

然后我们就用这个Next数组去匹配

void kmp()
{
    int i=0,j=0;
    int len1=strlen(str),len2=strlen(pat);
    while(i<len1)
    {
        if(str[i]==pat[j])
        {
            i++;j++;
        }else
        {
            j=Next[j];
        }
    }
}

最后再贴一个简单的模板题 POJ 3461

#include <iostream>
#include <cstring>
#include <cstdio>
#define cl(arr) memset(arr,0,sizeof(arr))
using namespace std;
const int maxpat=1e4+50;
const int maxstr=1e6+50;
int Next[maxstr];
char str[maxstr],pat[maxpat];
void getNext()
{
    int i=0,j=-1,len=strlen(str);
    Next[0]=-1;
    while(i<len)
    {
        if(j==-1||str[i]==str[j])Next[++i]=++j;
        else j=Next[j];
    }
}
int kmp()
{
    int i=0,j=0,len1=strlen(str),len2=strlen(pat);
    int ans=0;
    while(i<len1)
    {
        if(j==-1||str[i]==pat[j])
        {
            i++;
            j++;
        }
        else j=Next[j];
        if(j==len2)ans++;
    }
return ans;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",pat,str);
        getNext();
        printf("%d\n",kmp());
    }
return 0;
}

更新一波，当然由于模式串和目标串能匹配上的长度显然不会超过模式串的长度，
为了减少我们就NEXT的复杂度，我觉得我们只要求模式串的next即可

KMP 算法入门

全站热榜