我写的KMP算法代码

    技术2022-05-13  6

    #include<stdio.h>#include<string.h>

    int Index(char *s,char *t,int pos)  //普通算法{ int i = pos; int j = 0; int len1,len2; len1 = strlen(s); len2 = strlen(t); while (i<len1&&j<len2) {  if (s[i]==t[j])  {   ++i;   ++j;  }  else  {   i=i-j+1;   j=0;  } }    if (j>=len2)    {  return i-len2;    } else  {  return -1; }}void GetNext(char *t,int next[])   //获得next[]数组{ int i; int j; int len1;  len1 = strlen(t); i = 0; j = -1; next[0]=0; len1 = strlen(t); while (i<len1) {        if (j==-1||t[i]==t[j])        {   ++i;   ++j;   next[i]=j+1;        }  else  {   j = next[j]-1;  } }

    }int KMP(char *s,char *t,int next[])  //KMP算法{ int i = -1; int j = -1; int len1; int len2; len1 = strlen(s); len2 = strlen(t); while (i<len1&&j<len2) {  if (j==-1||s[i]==t[j])  {   ++i;   ++j;

      }  else  {   j = next[j]-1;  }

     } if (j>=len2) {  return i-len2; } else return -1;   }int main(){    int flag; int len; char *s = "acabaabcaabaabaabcacaabc"; char *t = "abaabcac";     int next[100]; len = strlen(t); GetNext(t,next); for (int i=0;i<len;i++) {  printf("%d ",next[i]); } printf("/n"); flag =  KMP(s,t,next); printf("%d/n",flag); return 0;}


    最新回复(0)