关于KMP算法的实现,如果转载请标明出处
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 #include <stdio.h> #include <stdlib.h> #include <string.h> #define OK 1 #define ERROR 0 #define status int typedef struct sstring { char ch[50]; int length; }Sstring, *Lstring; status InitString(Lstring& s); status GetString(Lstring s, Lstring p); status KMP(Lstring s, Lstring p, int pos, int* next); status KNext(Lstring p, int* next); int main() { Lstring s, p; int* next; InitString(s); InitString(p); GetString(s, p); next = (int*)malloc(sizeof(int) * (p->length+1)); next[0] = 0; KNext(p, next); if (KMP(s, p, 1, next)) { printf("存在"); } else { printf("不存在"); } return 0; } status InitString(Lstring& s) { s = (Lstring)malloc(sizeof(Sstring)); if (!s) { return ERROR; } s->length = 0; return OK; } status GetString(Lstring s,Lstring p) { char c[100]; printf("请输入主串:"); scanf("%s", &s->ch[1]); s->ch[0] = 'm'; s->length = strlen(s->ch)-1; getchar(); printf("请输入子串:"); s->ch[0] = 'm'; scanf("%s", &p->ch[1]); p->length = strlen(p->ch)-1; getchar(); return OK; } status KMP(Lstring s, Lstring p, int pos, int* next) { int i, j; i = pos; j = 1; while (i <= s->length && j <= p->length) { if (s->ch[i] == p->ch[j]) { i++; j++; } else if (j == 1) { i++; } else { j = next[j]; } } if (j > p->length) { return OK; } return ERROR; } status KNext(Lstring p, int* next) { int i, j; i = 1; j = 0; next[1] = 0; while (i <= p->length) { if (j == 0 || p->ch[i+1] == p->ch[j]) { j++; i++; next[i] = j; } else { j = next[j]; } } return OK; }
KMP算法的实现过程(被比对的是主串,比对的是字串)
从主串中查找是否含有子串
当比较 i 位置子串 和 主串中 k 位置的元素比较的时候
如果相同或者k = 0 的话 i++ k++ 继续比较下一个
如果不同的话,则让 k = next[k] 然后继续比较
直到 k 或者 i 超出子(主)串长度的时候停止比较
如果k超出范围的话 则比对成功
如果k没有超出范围的话,则比对失败
很多人不明白为什么 当比较不同的时候,KMP不用想BF算法那样 回到头从新开始比较,而是使用next数组回到对应的位置,下面我们来解释一下
其中最难实现的是 next 数组的获取:下面就我理解给大家讲一下
我们首先要懂得next数组的基本原理
next数组的基本原理就是:
当我们使用字串的第四个位置的元素和主串对应元素相比较的时候:
如果不相同的话,我们观察一下字串第四个位置和之前的元素有什么特点,明显的是 字串的一和二 和 字串的三和四相同,而且我们在子串和主串对应位置相比较的时候,当比较到字串的第四个位置的元素的时候,那么主串对应位置的前三个元素都和字串相同 ,所以我们不必返回 初始位置然后再从新比较, 我们只需要根据字串的特点来进行比较即刻,
由上面可知,在第四个位置和主串不相同的时候,那么 一二三位置的元素一定和主串位置元素相同,那么我们可以直接返回字串对应位置的next下标也就是2