KMP(看毛片?)

2019-10-06   数据结构

啥是看毛片? 呸! KMP?

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

KMP算法

视频教程:

B站 正月点灯笼 1
B站 正月点灯笼 2

建议非流量党观看!!!

关于最大公共前后缀:

B乎文字理解教程:

如何更好的理解和掌握 KMP 算法?

SDUT OJ题解:

1.数据结构实验之串一:KMP简单应用

#include<bits/stdc++.h>
using namespace std;

char a[1000005];
char b[1000005];

int Next[1000005];
void getNext(char b[],int len)//前缀表函数
{
    int i = 0;
    int j = -1;
    Next[0] = -1;
    while(i<len)
    {
        if(j==-1||b[i]==b[j])
        {
            i++;
            j++;
            Next[i] = j;
        }
        else
            j = Next[j];
    }
    return;
}
int KMP(char a[],char b[],int n,int len)
{
    getNext(b,len);
    int i = 0;

    int j = 0;

    while(i<n&&j<len)
    {
        if(j==-1||a[i]==b[j])
        {
            i++;
            j++;

        }
        else
            j = Next[j];
    }
    if(j==len)
        return i-len+1;
    return -1;
}
int main()
{
    while(~scanf("%s",a))
    {
        scanf("%s",b);
        int len1 = strlen(a);
        int len2 = strlen(b);
        int x = KMP(a,b,len1,len2);
        printf("%d\n",x);
    }
    return 0;
}

暂更至此!假期快结束了!

标签: KMP算法

上一篇:数据结构----栈与队列 下一篇:没有更多了


评论卡