KMP算法的实现详解

lovevivi

发布于 2022-11-10 14:39:43

5360

发布于 2022-11-10 14:39:43

文章被收录于专栏：萌新的日常

1.KMP算法

1.概念

KMP是一种改进的字符串匹配算法，该算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。

2.与BF(暴力算法)的的区别

暴力算法:模拟实现strstr函数当信息匹配失败时，主串i不会回退，子串j也不会回到0号位置

3.分析

1.j的回退位置

在下标为5时，信息匹配失败，此时i不回退，在此匹配失败，说明主串i与子串j下标5之前一定有一部分是相同的，此时j回退到下标为2的位置，继续向后就能匹配成功。

2.next数组

next[j]=k来表示，不同的 j 对应一个k值，k为要移动的 j 要移动的位置
寻找k规则： 1.匹配成功部分的两个相等的真子串(不包含本身)，一个以下标0开始，另一个以j-1下标开始结尾。 2.规定 next[0]=-1 ,next[1]=0, 正式计算是从下标2开始。

3.next数组的练习

1.练习1

注意事项

2.练习2

注意事项

一个小细节：一般来说next数组下标只会一个一个数加或者被赋值成0

4.推导过程

在next[i]=k的前提下

1.p[i]==p[k]

在p[0]......p[k-1] p[i-k]==p[i-1] ， next[i]=k的前提下 ....p[0]......p[k-1] p[k] == p[x]...p[i-1] p[i] ， next[i+1]=k+1

2.p[i]!=p[k]

回退到下标为2的位置，发现此时p[i]!=p[k]，则从当前位置继续回退，直到p[i]==p[k]，再通过next[i+1]=p[k+1]，确定p[i+1]对应的next下标数

4.代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
//str代表主串
//sub代表子串
//pos代表从当前位置
void getnext(char* sub,int*next,int lensub)
{
    next[0] = -1;
    next[1] = 0;
    int i = 2;//下一项
    int k = 0;//前一项的k
    while (i < lensub)
    {
        if (k==-1||sub[i - 1] == sub[k])//当k==-1时，说明第一个数不符合条件，进入循环后next[i]会被置成0
        {
            next[i] = k + 1;
            i++;
            k++;
        }
        else
        {
            k = next[k];
        }
    }
}
int KMP(char* str, char* sub, int pos)
{
    assert(str != NULL &amp;&amp; sub != NULL);
    int i = pos;
    int j = 0;
    int lenstr = strlen(str);//主串长度
    int lensub = strlen(sub);//子串长度
    int* next = (int*)malloc(sizeof(int) * lensub);
    assert(next != NULL);
    getnext(sub,next, lensub);
    while (i < lenstr &amp;&amp; j < lensub)
    {
        if (j==-1||str[i] == sub[j])//当一个数不符合条件时,此时就需要加入一个条件，否则就会造成越界
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j >= lensub)
    {
        return i - j;
    }
    return -1;
}
int main()
{
    char s1[40];
    char s2[40];
    scanf("%s%s", s1, s2);
    printf("%d\n", KMP(s1,s2,0));
    return 0;
}