KMP.zip_kmp效率

#include <stdio.h> typedef char* String; void get_next(String T,int *next) { int j = 0; int i = 1; next[1] = 0; while(i < T[0]) { if(0 == j || T[i] == T[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } } //返回子串T在主串S第pos个字符之后的位置，若不存在，则返回0 int Index_KMP(String S,String T,int pos) { int i = pos; int j = 1; int next[255]; get_next(T,next); while(i <= S[0] && j <= T[0]) { //主串与子串元素相等时,移至下一个元素进行匹配; if(0 == j || S[i] == T[j])//j=0时,T[j]是数组长度,j加1; { i++; j++; if(T[i] != T[j]) { next[i] = j; } else { next[i] = next[j]; } } else { j = next[j]; } } if(j > T[0]) { return (i - T[0]); } else { return 0; } } int main() { char ptr[255] = " baaaaab"; char str[255] = " aoiuybaaaaabcde"; int next[255]; int i = 1; str[0] = 15; ptr[0] = 7; int k; get_next(ptr,next); printf("子串的next数组元素为:\n"); for(i = 1;i <= ptr[0];i++) { printf("%d ",next[i]); } k = Index_KMP(str,ptr,0); if(k > 0) { printf("\n子串T在主串S中第pos个字符之后的位置为:%d",k); } else { printf("\n子串T在主串S中第pos个字符之后不再匹配"); } return 0; }