首页 > 代码库 > KMP

KMP

#include<stdio.h>#include<iostream>#include<string.h>using namespace std;void GetNext(char *str,int next[]){    int j,k;    j=0;k=-1;next[0]=-1;    while(str[j]!=‘\0‘)    {        if(k==-1 || str[j]==str[k])        {            j++;k++;            next[j]=k;        }        else k=next[k];    }}int KMPIndex(char *s,char *t){    int lent=strlen(t);    int next[100],i=0,j=0,v;    GetNext(t,next);    while(s[i]!=‘\0‘ && t[j]!=‘\0‘)    {        if(j==-1 || s[i]==t[j])        {            i++;j++;        }        else j=next[j];    }    if(j>=lent) v=i-lent;    else v=-1;    return v;}int main(){    char s[]="ababcabsds";    char t[]="abcd";    cout<<KMPIndex(s,t);    return 0;}

  

KMP