1、next()数组的原理

文章目录 三、next()数组的实现 四、主程序实现（c语言）

一、什么是KMP算法 二、KMP算法的运行原理 1、主串不回退

子串回退到特定位置

通过之前两个字符串，我们当发现主串的第四个字母与子串的第四个字母不同之后，主串不会退，子串回退到特定的位置。那么，这个特定位置是如何找到的呢？

这里我们重新设立两个字符串进行查找，并对它们标上相应的下标。

三、next()数组的实现 1、next()数组的原理

2、#代码实现（C语言）

void getnext(int* next, char* arr, int zi)
{next[0] = -1;next[1] = 0;int k = 2;int p = 0;while (i < zi){if (p == -1 || arr[k - 1] == arr[p]){next[k] = p + 1;k++;p++;}else{p = next[p];}}
}

四、主程序实现（c语言）

#include 
#include 
#include 
#include 
``char* kmp(char* arr1, char* arr2)
{assert(arr1);assert(arr2);int zhu = strlen(arr1);int zi = strlen(arr2);int i = 0;int j = 0;char* p = arr1;int* next = (int*)malloc(sizeof(int) * zi);assert(next);getnext(next, arr2, zi);if (zhu == 0){return NULL;}else if (zi == 0){return p;}while (i < zhu && j < zi){if (j == -1 || *(arr1 + i) == *(arr2 + j)){i++;j++;}else{j = next[j];}}if (j == zi){return p + i - j;}elsereturn NULL;
}int main()
{printf("%s\n", kmp("asdasdfgddasdd", "asddg"));printf("%s", kmp("asdasdfgddasdd", "asdd"));return 0;
}`