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

个人理解的kmp算法

程序员文章站 2022-07-03 12:42:53
kmp还是挺难上手的,看书加看博客,看了有五六篇才理解,看了大概四个小时。。#include #include #include using namespace std;//next数组本质是模式串中的前缀和后缀的相等数int next[555];//得到next数组的过程也是模式串自身匹配的过程void GetNext(char *p){ int plen=strlen(p);...

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

相关标签: 数据结构与算法