欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

KMP算法详解

程序员文章站 2024-03-17 17:37:34
...

KMP算法详解
相信KMP算法都有听过,但是理解这一算法确实有一定的难度,下面是我对KMP算法自己的一些理解,希望能对大家有帮助:
KMP算法详解

#include<iostream>
#include<cstring>
using namespace std;
void calnext(char *ptr , int *next , int len)  //len是ptr的长度,next数组储存的是从0到各个位置上,前后缀子串相等长度的数组
{
    next[0] = -1;   //只有一个字符的前后缀子串相同的情况不存在
    int k = -1;
    for(int i = 1 ; i < len ; i++)
    {
        while( k > -1 && ptr[k+1] != ptr[i])
    /*在下标为0到k的字符串中存在前后缀子串相同的情况,
      但在下标为0到i的字符串中,不存在该情况*/
        {
            k =  next[k];
    /*回溯,这部分需要好好体会 : 虽然在 0 到 i 的字符串中没有前后缀子串相同的情况
    但是,有可能在中间出现 ,
    例如 abcab D abcab C(D是下标为k+1的位置 , C为i的位置)
    满足上面的 k > -1 和 ptr[k+1] != ptr[i]的条件 (此时k为4),执行一次k = next[4] = 1(因为是下标,要-1),
    此时ptr[k+1] = p[2] = c , 而 ptr[i] = c , 所以匹配 , 退出循环 , 此时k = 1 ,再执行
    下面的if( ptr[k+1] == ptr[i]) k++; 后便可得到k = 2*/
    /*这里要注意的是:因为此时的k是4的话,
    在位置0到i-1上,前后缀子串相等长度就已经有5了,如果在前五个字符中也可以做到前后缀字符串匹配的话,
    就可以保证第一个ab会等于第四个ab(ABcAB d ABcAB c)
    所以就是比较k+1位置上的字符和i上的字符是否相等,
    相等: 就退出while循环 , 在下面的if操作中给k+1;
    不相等: 就再进行while循环,在给k赋值为0到k位置上前后缀子串相等的长度,
    如果是-1的话就跳出while循环,
    进行下面的if判断,判断第一个字符是否和第i个字符相等*/
        }
        if(ptr[k+1] == ptr[i])  //如果相等,则前后缀子串相等长度加一
            k++;
        next[i] = k;  //在0到i的字符串中,有长度为k的子串字符相等
    }
}
int KMP(char *str , char *ptr)
{
    int len1 = strlen(str);
    int len2 = strlen(ptr);
    int k = -1;
    int *next = new int[100];
    calnext(ptr , next , len2);
    for(int i = 0 ; i < len1 ; i++)
    {
        while( k > -1 && str[i] != ptr[k+1])  //此处的意思为两个字符串有重叠部分但是不相等
        {
            k = next[k];  /*这里也很玄妙(长度预警)
            这里也用一个例子来说明,str: abb...ab B  ptr: abb...ab C,
            此时 k+1 是B的位置, i是C的位置,此时满足while循环的条件,让
            k = next[k] = 1 (前面的next函数已经得到了),然后比较ptr[2] 和 str[i]是否相等
            相等:则跳出while循环,并在下面的if语句中实现k++;
            不相等:继续进行while循环,将next[1]的值赋给k,然后在进行判断,是否满足循环条件*/
            /*这里需要说明的是:KMP算法是跳过了中间的一格一格的移动比较,而是通过计算前缀和
            后缀相等的长度来进行(上面已经通过图解来说明),本来比较字符串的
            时间复杂度大致为O(m*n),通过KMP算法吧这一过程优化成了O(m+n)*/
        }
        if(str[i] == ptr[k+1])
            k++;
        if(k == len2 - 1)
            return i - k;
    }
    return -1;
}
int main()
{
    char str[100] , sstr[20];
    cin>>str;
    cin>>sstr;
    cout<<KMP(str,sstr);
    return 0;
}
相关标签: KMP 算法

上一篇: 前端性能优化总结

下一篇: KMP算法