KMP
思路
在经典的字符串匹配中，如果字符匹配失败i会返回到开始匹配时的后一个字符。这样会导致效率的下降。在KMP算法中，即使匹配失败i也不会动，只会J进行移动。
在匹配的过程中，字符相同时，就会进行下一对字符的匹配。当不相同时，如下面：
匹配失败，此时j需要回退，要回退到哪里呢？回退到下标为2的地方处。 原因如下： i前面的字符都是匹配成功的，j前面的字符也是匹配成功的。常规情况下j要从头开始进行匹配，如果发现j前面的子串存在两个相同的真子串时（以下标0开始，以下标j-1结束），那么j就退回到真子串长度的位置处。如下面：
近一步解释，i前面的串和j前面的串相等，匹配时一定是从下标为0的位置匹配的，这也是找——以下标0开始，以下标j-1结束串——的原因，如果存在这两个串，则说明i前面一定存在以下标0开始，以下标j-1结束串的子串。这样J退回的时候就省去了从头开始进行匹配。
这个串每个字符都有可能进行回退。回退的位置用一个数组进行储存，就形成了next数组
next数组
默认：0号位回退到-1处（在代码中处理，将不会造成数组越界问题) 1号位匹配失败退到0处。 现在主要的问题是如何实现next数组。
我们用K表示返回位置的下标，p是字符串，j表示下标。 假设next[j]=k成立(表达在j处匹配失败后返回到以k为下标处的位置) 那么p[0]····p[k-1]==p[x]····p[j-1] (k处位置是从新匹配的地方，它前面的子串一定和j前面的子串相同) 从上面那个式子可以看出k-1-0=j-1-x即x=j-k; 式子就变成了p[0]····p[k-1]==p[j-k]····p[j-1] ——>next[j]=k成立的情况下 1️⃣当p[j]=p[k] 上面的式子可以变成p[0]····p[k-1] p[k]==p[j-k]····p[j-1] p[i]——>next[j+1]=k+1 2️⃣当p[j],p[k]不相等时，就会回退到k处，如果此时的k所对应k1，p[k1]=p[j] 那么next[j+1]=k1+1,否则继续回退，直到相等或者为-1处停止。 经过这样的过程，我们就得到了next数组
下面用图片给以进一步解释：下面的i是j，手残写错字母了。
next数组优化——>nextval数组
nextval数组的实现是根据next数组来实现的。 具体的求法：nextval数组的第一个元素为-1，第二个元素位0，以后j下标所对应的字符如果和以k对应的字符相等，那么nextval的元素为nextval[k]中的元素。如果不相等，nextval的元素为next里面的元素(即为k的值)。
nextval数组
cvoid my_nextval(int* nextval, char* p, int n)
{
int k = -1, j = 0;
nextval[0] = -1;
while (j < n)
{
if (k == -1|| p[j] == p[k])
{
j++;
k++;
nextval[j] = k ;
if (p[j] != p[k])
nextval[j] = k;
else
nextval[j] = nextval[k];
}
else
{
k = nextval[k];
}
}
}代码实现
c#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
void my_next(int* next,int n,const char* p)
{
int j = 0,k=-1;
next[0] = -1;
while(j<n)
{
if (k == -1 || p[j] == p[k])
{
next[j + 1] = k + 1;
j++;
k++;
}
else
{
k = next[k];
}
}
}
int kmp(const char* str1, const char* str2)
{
int i = 0, j = 0;
int len = (int)strlen(str2);
//next数组
int* next = (int*)malloc(len * sizeof(int));
assert(next);
my_next(next,len-1,str2);
while (str2[j])
{
if(j==-1||str1[i] == str2[j])
//j为-1时该位置下的i不会匹配成功，进入下一次匹配
{
i++;
j++;
}
else
{
j = next[j];//j进行回退
}
if (str1[i] == '\0')
{
free(next);
next = NULL;
return -1;
}
}
free(next);
next = NULL;
return i;
}
int main()
{
char arr[] = "abaabcdabcab";
char brr[] = "ef";
printf("%d\n",kmp(arr, brr));
return 0;
}腾讯云开发者
