什么是KMP算法：
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1] 。
------来自百度百科
要了解KMP算法，我们首先了解一下传统BF算法。
BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。
- -----来自百度百科
BF算法是怎么样的呢。我们先用一幅图解释一下。
以C语言库函数strstr为例我们用BF算法模拟实现一下。
char * strstr (const char * str1, const char * str2) {
char *cp = (char *) str1;
char *s1, *s2;
if ( !*str2 )
return((char *)str1);
while (*cp)
{
s1 = cp;
s2 = (char *) str2;
while ( *s1 && *s2 && !(*s1-*s2) )
s1++, s2++;
if (!*s2)
return(cp);
cp++;
}
return(NULL);为什么乘BF算法为蛮力算法呢！我们来了解一下KMP算法与它的主要区别。
KMP和BF的根本区别就在于，主串的i是不会回退的，而j视情况回退。
我们观察上图，当匹配到5位置时，匹配失败，既然能匹配到此位置说明至少子串j之前的部分必定是相同的。博友们仔细体会一下这句话。
观察上图，如果i不回退，j回退到2位置是不是就是最好的情况，因为子串2位置之前的部分就等于主串i前面的部分。相比于BF算法减少了很多不必要的工作，使得程序更加高效。那我们如何能知道在5位置匹配失败后就让j回退到2位置呢。
那我们就顺利的引出了KMP算法的精髓next数组：也就是用next[j]=k;来表示不同的j来对应一个k值，这个k值就是将来要移动的j所要移动到的位置。
我们的k值是这样求得：
1.规则：找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标0开始，另一个以下标j-1结尾。
2.不管什么数据next[0] = -1,next[1] = 0,
给博友们两个练习，答案就在下方，了解一下next数组的求法：
设主串为数组a，子串为数组b。我们假设next[j] = k的话那就有，b[0]b[1]...b[k-1] = a[x]a[x+1]...a[i-1]。假设a[i]=b[k]的话，b[0]b[1]...b[k-1]b[k] = a[x]a[x+1]...a[i-1]a[i],那就有next[j+1] = k+1.那现在只要能知道a[i]!=b[k]时next[j+1]即可。当a[i]!=b[k]时我们令k=next[k],再去比较next[j+1] = k+1，直到k=-1时都无法匹配，那么next[j+1]=0.
至此为止我们已经知道next数组的求法。我们利用KMP算法重新实现strstr函数
void get_next(char* sub,int* next, int size)
{
next[0] = -1;
next[1] = 0;
int i = 2;
int k = 0;
while (i < size)
{
if (k==-1||sub[i - 1] == sub[k])
{
next[i] = k + 1;
i++;
k++;
}
else
{
k = next[k];
}
}
}
//str1:代表主串；
//str2:代表子串，
char* my_strstr(const char* str1, const char* str2)
{
char* start = str1;
assert(str1 != NULL && str2 != NULL);
int* next = malloc(sizeof(int) * strlen(str2));
int lenStr = strlen(str1);
int lenSub = strlen(str2);
if (lenStr == 0 || lenSub == 0) return NULL;
get_next(str2, next, strlen(str2));
int i = 0, j = 0;
while (i < lenStr && j < lenSub)
{
if (j == -1 || str1[i] == str2[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j == lenSub)
return start + (i - j);
}
int main()
{
char arr[20] = "100866666";
char arr2[] = "866";
//int* k = malloc(sizeof(int));
printf("%s", my_strstr(arr, arr2));
return 0;
}运行结果如下。
不足之处欢迎博友们指正！