房地产公司网站建设与推广方案,2022百度收录越来越难了,tp框架做购物网站开发,申请网站域名什么是kmp算法 1.kmp算法是一种改进的字符串算法#xff0c;其核心是利用匹配失败后的信息#xff0c;尽量减少模式串与主串的匹配次数已达到快速匹配的目的。 它主要实现作用的是 在 #xff08;主串#xff09;中找到 #xff08;匹配#xff09;字符串。 例 BF算法与k…
什么是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[i1] k1 ,如果 p[i] ! p[k] 则 next[k] ! k, knext[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;
}
