正文

kmp模板

claireyuancy  claireyuancy  2022-09-05  201

关键词：

KMP算法是高速字符串匹配算法，朴素的暴力算法的时间复杂度为O（n*m）。而KMP通过对模式串进行对应的处理，可以达到O（m+n）的速度。

我们知道在字符串匹配的时候最消耗时间的就是当匹配到第 i 个位置发现不匹配时。下一次又对模式串进行一次又一次匹配，那么假如模式串中有非常多同样的字母的话，这样做了非常多反复的事情，那么我能够对模式串进行一定的处理。处理处一个相应的数组。让他保存假如这里不匹配是我下次应该从哪儿又一次開始。

每次当前的一个值是依据前面是否匹配的到。

这是预处理函数：

void getfill(string s)
{
    memset(f,0,sizeof(f));  //依据其前一个字母得到
    for(int i=1;i<s.size();i++)
    {
        int j=f[i];
        while(j && s[i]!=s[j])
            j=f[j];
        f[i+1]=(s[i]==s[j])?
j+1:0;
    }
}

然后匹配函数就非常好写了、

int find(string a,string s)
{
    
    getfill(s);int j=0;
    for(int i=0;i<a.size();i++)
    {
        while(j && a[i]!=s[j])
            j=f[j];
        if(a[i]==s[j])
            j++;
        if(j==s.size()){
            return i-s.size()+1;
        }
    }
}

顺便贴一道联系题目：

poj3461 。求一个模式串在字符串中的出现次数。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include <iostream>
#include <string>
using namespace std;
int f[ 15000];
void getfill(string s)
{
    memset(f,0,sizeof(f));  //依据其前一个字母得到
    for(int i=1;i<s.size();i++)
    {
        int j=f[i];
        while(j && s[i]!=s[j])
            j=f[j];
        f[i+1]=(s[i]==s[j])?j+1:0;
    }
}
int find(string a,string s)
{
    int ans=0;
    getfill(s);int j=0;
    for(int i=0;i<a.size();i++)
    {
        while(j && a[i]!=s[j])
            j=f[j];
        if(a[i]==s[j])
            j++;
        if(j==s.size()){
            ans++;
        }
    }
    return ans;
}
int main()
{
    string s,a;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        getchar();
        cin>>s>>a;
        int ans=find(a,s);
        printf("%d
",ans);
    }
    return 0;
}

kmp模板

...include<bits/stdc++.h>usingnamespacestd;/*************************KMP模板****************************/intf[101];//优化后的失配指针,记住这里f要比P多一位,因为P到m-1即可,但是f还要计算出m的失配指针intf2[101];//f2用来保存KM指针，是为优化f的失配指... 查看详情

扩展kmp模板

扩展KMP指的是对于给出的串S和T，以O(n)的时间求出。对于所有0<=i<len(S),S(i,i+1,...,len(s)-1)与T的最长前缀长度。以下是模板：#include<iostream>#include<string>#include<stdio.h>#include<string.h>usingnamespacestd;c 查看详情

模板kmp算法

KMP算法用于字符串匹配1/*KMP*/2#include<stdio.h>3#include<string.h>4chars1[1000005],s2[1005];//s1为待匹配串，s2为模板串5intnxt[1005],n,m;6intmain()7{8scanf("%s%s",s1+1,s2+1);9n=strlen(s1+1);m=strlen(s2+1);10n 查看详情

kmp模板(代码片段)

今天又加深的理解了KMP认真看了这篇博客，感觉讲的还ok；然后带着理解写了洛谷的P3375字符串KMP模板题；#include<iostream>#include<cstdio>usingnamespacestd;constintmaxn=1e6+9;stringt,s;intNext[maxn];voidget_next()intlen=s.length();intk= 查看详情

算法模板之kmp

KMP#include<cstdio>#include<cstring>voidget_next(char*p,int*next){intpLen=strlen(p);next[0]=-1;intk=-1,j=0;while(j<pLen-1){if(k==-1||p[j]==p[k]){j++;k++;next[j]=k;}else{k=next[k];}}}int 查看详情

扩展kmp模板(代码片段)

...extend[i].具体extend的求法就不具体写了,这里只写求extend的模板.模板用到的数组charT[N 查看详情

扩展kmp模板(代码片段)

...extend[i].具体extend的求法就不具体写了,这里只写求extend的模板.模板用到的数组charT[N 查看详情

kmp模板(代码片段)

KMP的c++版模板例题HDU5918 http://acm.hdu.edu.cn/showproblem.php?pid=59181template<typenamefirst_T,typenamesecond_T>2voidkmp_init_next(constfirst_T*dec,3intdlen,4second_Tnext[])5inti,j;6j=next[0] 查看详情

扩展kmp模板(代码片段)

具体原理可以参考这里：扩展KMP、扩展KMP算法（刘毅）代码：1#include<iostream>2#include<cstdio>3#include<cstring>4#include<algorithm>5usingnamespacestd;6constintN=1e6+5;78intlen1,len2;9intnxt[N],extend[N] 查看详情

kmp模板~

#include<cstdio>#include<cstring>#include<iostream>#include<queue>#include<map>usingnamespacestd;intNext[100010];strings[100010];voidgetNext(strings){inti,j;i=0;j=-1;intl 查看详情

kmp模板

详解：http://www.cppblog.com/oosky/archive/2006/07/06/9486.htmlhttp://www.matrix67.com/blog/archives/115http://blog.csdn.net/v_july_v/article/details/7041827http://kb.cnblogs.com/page/176818/白书上的代码：#incl 查看详情

模板kmp

不断向失配处转移#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#definemaxn1000005usingnamespacestd;chart[maxn],p[maxn];intf[maxn];voidgetfail(char*p,int*f){intm= 查看详情

hdu2087剪花布条kmp模板题

...复制了……刚好数据结构也学了kmp找一道题敲敲模板……暴力的字符串匹配是O(n*m)的时间复杂度而kmp通过一个O(m)的预处理将字符串匹配的时间复杂度降到了O(n+m)kmp的核心是next数组的处理和利用next数组进行字符串... 查看详情

kmp模板

//kuangbin的模板：intS[maxn];intT[maxn];intnext_[maxn];inttlen,slen;voidGetNext(){intk=-1;next_[0]=-1;intj=0;while(j<tlen){if(k==-1||T[j]==T[k])next_[++j]=++k;elsek=next_[k];}}//返回第一个匹配字符串的起始位置下标intKMP 查看详情

kmp模板(代码片段)

/*pku3461(Oulipo),hdu1711(NumberSequence)这个模板字符串是从0开始的Next数组是从1开始的*/#include<iostream>#include<cstring>usingnamespacestd;constintN=1000002;intnext[N];charS[N],T[N];intslen,tlen;voidgetNext 查看详情

kmp算法模板

#include<stdio.h>#include<string.h>typedefstructseqstring{charstring[100];intlength;}seqstring;voidgetnext(seqstringp,intnext[]){inti,j;next[0]=-1;//next[0]放上-1i=0;//指向字符串每个字符的指针j=-1;while 查看详情

kmp模板

#include<iostream>#include<cstdio>#include<cstring>#definemxn1000001usingnamespacestd;charT[mxn],P[10001];intf[mxn];voidgetfail(){inti,j,m=strlen(P);for(i=1;i<m;i++){intj=f[i];whi 查看详情

kmp模板及总结

KMP是一种字符串匹配算法，它在时间复杂度上较暴力匹配算法由很大的优势。比如我要找字符串S中是否存在子串P，如果暴力匹配的话，则时间复杂度为O（n*m），而kmp算法时间复杂度为O（n+m）。这里我们有一个辅助的数组next[]... 查看详情