学习笔记-KMP算法

按照学习计划和TimeMachine学长的推荐，学习了一下KMP算法。

昨晚晚自习下课前粗略的看了看，发现根本理解不了高端的next数组啊有木有，不过好在在今天系统的学习了之后感觉是有很大提升的了，起码能打出模板了。。。（无奈）

KMP算法是一种字符串匹配算法，能够最坏在线性时间跑出答案的算法，时间复杂度为O（n+m)

对于字符串匹配，原始的套路在于两个串直接枚举起来。当要被查询的串T【】与查询串P【】的首字母匹配时便依次比较下去，一旦失配后T【】串的下标+1继续找，直到找到为止

KMP算法的做法也是如此，只不过在失配后会进行额外的跳跃，避免了大量的冗余操作，节约时间，而对于要跳跃的步数则引入next数组初始化后得出。

具体的讲解还是参见此blog：http://www.cnblogs.com/c-cloud/p/3224788.html

（博主写的非常通俗易懂，但是Bi~（NTMD）能不能不要把标程写残啊，坑人啊！！）

当然还是Matrix67神犇的讲解更加为人信服：http://www.matrix67.com/blog/archives/115

下面是个模板，查询串在被查询串中出现的次数。：

【get_next过程初始化出next数组（通用）；KMP过程进行匹配（根据不同题目对统计的答案进行修改即可）】

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

char t[1000010], p[1000010];

int next[1000010];

int n,m;int ans;

void get_next()

{

    int k=-1;

    int j=0;

    next[0]=-1;

    while (j<m)

    {

        if (k==-1 || p[j]==p[k])

        {

            j++;

            k++;

            if (p[j]!=p[k])

                next[j] = k;

            else

                next[j] = next[k];

        }

        else

            k=next[k];

    }

}

void kmp()

{

    int i=0,j=0;

    while (i<n)

    {

        if (j==-1 || p[j]==t[i])

        {

            i++;

            j++;

        }

        else

            j = next[j];

        if (j==m)

        {

            ans++;

            j=next[j];

        }

    }

}

int main()

{

    int time;

    scanf("%d",&time);

    while (time--)

    {

        scanf("%s",p);

        scanf("%s",t);

        n=strlen(t);

        m=strlen(p);

        get_next();

        ans=0;

        kmp();

        printf("%d\n",ans);

    }

    return 0;

}

学习笔记-KMP算法的相关教程结束。