#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;}
