数据结构与算法系列之kmp算法

什么是kmp算法

1.kmp算法是一种改进的字符串算法，其核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数已达到快速匹配的目的。
它主要实现作用的是 在 （主串）中找到 （匹配）字符串。
例

BF算法与kmp算法的差别

bf算法如下所示 从首元素字符开始依次比较 ，如果相同则比较下一位元素，如果匹配失败 ，匹配字符串从头开始 ，主串从第二个字符开始比较，直到主字符串全部匹配完。如果匹配成功返回主字符串中第一次出现匹配字符串的位置。

kmp算法如下所示，kmp与bf不一样的地方在于：主串的所指向的字符不会后退，匹配串中所指向的也不会移动到首字符位置

kmp的回退规则，next数组的介绍

目的是使 指向主串字符不会回退 ，匹配串回退到一个特定位置

这就是next数组的来源
规定next[0]=-1 next[1]=0

回退前提 : p[i] == p[k] 则 p[i] == p[k] next[i+1] == k+1 ,如果 p[i] != p[k] 则 next[k] != k, k==next[k] ,一直回退直到p[i] == p[k]

p[i] == p[k] 如下

p[i] != p[k]如下

kmp算法代码实现（C语言版）

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
void GetNext(char*sub, int* next ,int LenSub)
{next[0] = -1;next[1] = 0;int k = 0;int i = 2;while(i < LenSub){if (k == -1 || sub[i - 1] == sub[k]){next[i] = k + 1;i++;k++;}else{k = next[k];}}
}
int KMP(char* str, char* sub, int pos)
{assert(str  && sub );int LenStr = strlen(str);int LenSub = strlen(sub);if (LenStr == 0 || LenSub == 0)return -1;if (pos < 0 || pos >= LenStr)return -1;int* next = (int*)malloc(sizeof(int) * LenSub);assert(next);GetNext(sub, next,LenSub);int i = pos;//主串int j = 0;//字串while (i < LenStr && j < LenSub){if (j == -1 || str[i] == sub[j]){i++;j++;}else{j = next[j];}}if (j >= LenSub)return i - j;return -1;
}int main()
{printf("%d", KMP("ababcabcdabcde", "abcd", 0));return 0;
}