KMP算法模板（草解）

在长度为N的字符串中匹配长度为m的字符串，KMP算法是在任何的字符串中匹配中时间复杂度都是O(m+n),不会出现极致的情况O（n*m）

简单得讲他就是先对字符串N进行预处理，从而在与字符串M匹配时跳过一些字符串，从而达到快速匹配的目的

他是怎么实现的呢？

假设指针i指向字符串N,j指向字符串M的位置，在使用KMP算法时，指向N的i指针是不会回溯的，而是一直往后面走，大大减少了时间复杂度,-------KMP的核心就是Next[]数组的使用，，当出现失配后，当进行下一次匹配时，用Next[]指出j回溯的位置

首先要理解Next数组的含义：next[i]表示前面长度为i的子串中，前缀和后缀相等的最大长度，前缀和后缀一定要分别包含前一个和最后一个。不懂前缀和后缀的可以去看下面的教学视频

KMP模板题目：HDU-2087减花布条

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const ll maxn=10005;
char str[maxn],pattern[maxn];
int cnt;
int nexts[maxn];
void getNext(char *p,int plen){//预处理nexts,用于在失配的情况下得到j回溯的位置
    nexts[0]=0,nexts[1]=0;
    for(int i=1;i<plen;i++){
        int j=nexts[i];
        while(j&&p[i]!=p[j]) j=nexts[j];
        nexts[i+1]=(p[i]==p[j])?j+1:0;
    }
}
void kmp(char *s,char *p){
    int last=-1;
    int slen=strlen(s),plen=strlen(p);
    getNext(p,plen);//先对nexts数组进行预处理
    int j=0;
    for(int i=0;i<slen;i++){//匹配S和P的每个字符
        while(j&&s[i]!=p[j])j=nexts[j];//失配了就用nexts找回j的回溯位置
        if(s[i]==p[j])j++;//当前字符串匹配，继续
        if(j==plen){//完全匹配
        //printf("at location=%d %s\n",i+1-plen,&s[i+1-plen]);
            if(i-last>=plen){//下面是本题相关的代码，前面都是模板
                cnt++;
                last=i;//last指向上一次匹配的末尾位置
            }
        }
    }
}

int main(){
    while(~scanf("%s",str)){
        if(str[0]=='#')break;
        scanf("%s",pattern);
        cnt=0;
        kmp(str,pattern);
        printf("%d\n",cnt);
    }
}

           

哔哩哔哩教学视频