KMP算法看懂了觉得特别简单,思路很简单,看不懂之前,查各种资料,看的稀里糊涂,即使网上最简单的解释,依然看的稀里糊涂。
KMP算法充分利用了目标字符串ptr的性质(比如里面部分字符串的重复性,即使不存在重复字段,在比较时,实现最大的移动量)。
kmp算法主要是next数组的计算
代码分析:
#include <stdio.h> #include <string.h> int next[32] = {-999}; void print_next(int next[], int n) { for (int i = 0; i < n; i++) { printf("next[%d] = %d ", i, next[i]); } } void getNext(char* arrays) { int i = 0,j = -1; next[i] = j; while(i<strlen(arrays)) { if(j==-1||arrays[i] == arrays[j]) { i++; j++; next[i] = j; } else { j=next[j]; } } } int KMP(char* arrays1,char * arrays2) { int i = 0,j = 0; while(i<strlen(arrays1)&&j<strlen(arrays2)) { if(arrays1[i]==arrays2[j]||j==-1) { i++; j++; }else{ j=next[j];} } if(j==strlen(arrays2)) return i - strlen(arrays2); return -1; } int main(void) { char *s = "ababcabcacbab"; char *t = "abcac"; int index; getNext(t); print_next(next, strlen(t)); index = KMP(s, t); printf("index = %d ", index); }