首页 > 代码库 > KMP-模式匹配

KMP-模式匹配

发板子~

struct KMP{//s为子串,t为原串    static const int N=10100;    int next[N];    void getnext(char *s){        int lens=strlen(s);        next[0]=next[1]=0;        for(int i=1;i<lens;i++){            int j=next[i];            while(j&&s[i]!=s[j])j=next[j];            next[i+1]=s[i]==s[j]?j+1:0;        }    }    int kmp(char *s,char *t){        int lens=strlen(s),lent=strlen(t),ans=0;        for(int i=0,j=0;i<lent;i++){            while(j&&s[j]!=t[i])j=next[j];            if(s[j]==t[i])j++;            if(j==lens)ans++;//可重子串 else bu→j=0;        }        return ans;    }}kmp;

  

KMP-模式匹配