/** * 看了 b站视频 BV1jb411V78H 对KMP有了一点理解，然后我写了这个代码 * 这个代码和视频里面的有一点不同，字符串是从 0 开始的，而不是从1 开始的 * 希望能够帮到学习KMP的人 */ #include <stdbool.h> #include <malloc.h> #include "KMP.h" // KMP.h 内容 /* #define MAXSIZE (255) typedef struct { char ch[MAXSIZE + 1]; int length; }SString; void Next(SString const *t); extern int *next; int IndexOf_KMP(SString const *s, SString const *t); */ int *next; // 计算 next数组 /** * 计算 0-based 模式串t的next数组 * @param t 模式串 */ void Next(SString const *t) { // 模式串 0 开始 int length = t->length; // 分配 next数组 所需要的空间 next = (int *)malloc(sizeof(int) * length); for (int *p = next; p < next + length; p++) { *p = 0; } for (int i = 0; i < length; i++) { if (i <= 1) // 前两个next[i]置为-1 { next[i] = -1; continue; } // 执行下面的语句的时候， 一定有 i >= 2 int maxlen = 0; // 存储最长公共前后缀的长度 /** * // len 表示前缀或后缀的最大长度, 可取的值是 [1..i-1] // i 为(模式串或next数组)的访问下标 * 这里主要是 对 模式串在i位置 求 它的最大公共前后缀的长度 * 从 1 开始 到 i-1 一个一个去试 * */ for (int len = 1; len < i; len++) { int val = 0; bool flag = false; for (int j = 0, k = i - len; j < len; j++, k++) { if (t->ch[j] == t->ch[k]) { } else { flag = true; // len 长度的公共前后缀匹配失败 break; } } if (flag == false) // 公共前后缀长度为len val = len; if (val > maxlen) // 这个比较不是必须的，因为找公共前后缀的长度的时候， len 从 1 到 i-1 maxlen = val; // maxlen 就是 next[i]的值了 } next[i] = maxlen; } } // 调用这个函数之前，一定要调用 Next函数，为模式串构建 next数组 int IndexOf_KMP(SString const *s, SString const *t) { // 开始匹配 int i = 0, j = 0; // i 表示主串的下标， j 表示模式串的下标 while (i < s->length) { if (j == -1 || s->ch[i] == t->ch[j]) { i++; j++; } else { j = next[j]; } // 匹配成功 if (j == t->length) { return i - t->length; } } // 匹配失败 return -1; }