当前位置： 移动技术网 > 移动技术>移动开发>IOS > 个人理解的kmp算法

个人理解的kmp算法

2020年07月23日  | 移动技术网移动技术  | 我要评论

kmp还是挺难上手的，看书加看博客，看了有五六篇才理解，看了大概四个小时。。

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

//next数组本质是模式串中的前缀和后缀的相等数
int next[555];

//得到next数组的过程也是模式串自身匹配的过程
void GetNext(char *p)
{
    int plen=strlen(p);
    next[0]=-1;
    //k为前缀，j为后缀
    int k=-1;
    int j=0;
    while(j<plen-1)
    {
        if(k==-1||p[j]==p[k])
        {
            k++;
            j++;
            if(p[j]!=p[k])
            next[j]=k;
            else next[j]=next[k];
        }
        else
        {
            k=next[k];
        }
    }
}

int kmp(char *s,char *p)
{
    int i=0;
    int j=0;
    int sLen = strlen(s);
    int pLen = strlen(p);
    while(i<sLen && j < pLen)
    {
        if(j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else//若是字符不匹配
        {
            //这里相当于将j减去一个j-next[j]
            //联想一下那个匹配的图，主串不动，模式串变化，即为模式串相当于主串滑动
            //即相当于模式串向右滑动了j-next[j]位
            j = next[j];
        }
    }
    if(j == pLen)
        return i - j;
    else
        return -1;
}

int main()
{
    char a[555],b[555];
    cin>>a>>b;
    GetNext(b);
    int n=kmp(a,b);
    printf("%s",a+n);
    return 0;
}

本文地址：https://blog.csdn.net/zhoucheng_123/article/details/107479319

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网