目录
前言：
我们应该知道字符串函数strstr---字符串查找，实现它的有两种方法：
第一种方法：BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?-------来自百度
第二种方法：KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)?[1]??。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? -------来自白度?
BF算法
BF算法的图文解析
?BF算法的代码实现
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
int BF(char *str, char *sub)
{
assert(str != NULL && sub != NULL);
if (str == NULL || sub == NULL)
{
return -1;
}
int i = 0;
int j = 0;
int strLen = strlen(str);
int subLen = strlen(sub);
while (i < strLen && j < subLen)
{
if (str[i] == sub[j])
{
i++;
j++;
}
else
{
//回退
i = i - j + 1;
j = 0;
}
}
if (j >= subLen)
{
return i - j;
}
return -1;
}
int main()
{
printf("%d\n", BF("ababcabcdabcde", "abcd"));
printf("%d\n", BF("ababcabcdabcde", "abcde"));
printf("%d\n", BF("ababcabcdabcde", "abcdef"));
return 0;
}KMP算法
在学习kmp算法之前，我们更需要理解一下它的逻辑；我们这里讲解主要从三个版块：next数组的代码实现，kmp算法的代码实现，主函数对kmp的调用；关于next数组也需要从三个方面介绍：如何算next数组，next数组的结论，next结论在代码的实现；关于kmp算法代码实现我们主要需要知道：bf算法与kmp算法的不同之处，kmp算法的实现。
算next数组
练习 1： 举例对于”ababcabcdabcde”， 求其的 next 数组？
-1 0 0 1 2 0 1 2 0 0 1 2 0 0
练习 2： 再对”abcabcabcabcdabcde”,求其的 next 数组？ "----不做讲解， 自己实现
-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0
练习 1的图文讲解
?next数组的结论讲解
?next数组的创建
?创建next数组有两种情况：
1.如果p[i]==p[k]->next[i]=k;
? 2.如果p[i]!=p[k]->next[i]=k;
?
代码实现?
void GetNext(int *next, const char *sub)
{
assert(next&&sub);
int sublen = strlen(sub);
next[0] = -1;
next[1] = 0;
int i = 2;
int k = 0;
while (i < sublen)
{
if ((k == -1) ||sub[i - 1] == sub[k])//两种情况1.如果next数组下标是与k相等，那么就等于k+1 这个是next数组的性质
//2.如果不相等,将test中k的坐标赋予k
{
next[i ] = k + 1;//
i++;
k++;
}
else
{
k = next[k]; //列如最开始sub数组中i和k的值就不相等，这里k=0；next[k]=-1;k=-1+1=0;next[i]=0;
}
}kmp代码实现讲解
为什么主串不回退？?
?假设目前在2号位置匹配失败，就算回到1的位置，也是没有必要的，1的位置字符b和子串0的位置a也不一样。所以我们移动i是没有必要的。
子串退回位置
?此时匹配失败，我们不进回退i，因为在这个地方匹配失败，说明i的前面和j前面，是有一部分相同的，不然两个下标是不可能走到这里来的。 所以我们看这个图如果j退回到这里是最好。
kmp阶段的代码
int KMP(char* str,const char* sub, int pos)//pos是不会变的，指向sub中的地址
{
assert(str&&sub);
int i =pos;//遍历主串
int j =0;//遍历子串
int slen = strlen(str);
int sublen = strlen(sub);
int* next = (int*)malloc(sublen*sizeof(int));
assert(next);
if (next == NULL)
{
return - 1;
}
GetNext(next, sub);
while (j < sublen && i < slen)
{
if ((j == -1) || str[i] == sub[j])
{
i++;
j++;
}
else
{
j = next[j];//因为next数组的特性，其中有重复，每次不相等就将j的next数组的坐标重新赋予到j进行比较，
}
}
free(next);
if (j >= sublen)
{
return i- j;
}
else
{
return -1;
}
}KMP的代码汇总? ? ?
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
void GetNext(int *next, const char *sub)
{
assert(next&&sub);
int sublen = strlen(sub);
next[0] = -1;
next[1] = 0;
int i = 2;
int k = 0;
while (i < sublen)
{
if ((k == -1) ||sub[i - 1] == sub[k])//两种情况1.如果next数组下标是与k相等，那么就等于k+1 这个是next数组的性质
//2.如果不相等,将test中k的坐标赋予k
{
next[i ] = k + 1;//
i++;
k++;
}
else {
k = next[k]; //列如最开始sub数组中i和k的值就不相等，这里k=0；next[k]=-1;k=-1+1=0;next[i]=0;
}
}
}
//
int KMP(char* str,const char* sub, int pos)//pos是不会变的，指向sub中的地址
{
assert(str&&sub);
int i =pos;//遍历主串
int j =0;//遍历子串
int slen = strlen(str);
int sublen = strlen(sub);
int* next = (int*)malloc(sublen*sizeof(int));
assert(next);
if (next == NULL)
{
return - 1;
}
GetNext(next, sub);
while (j < sublen && i < slen)
{
if ((j == -1) || str[i] == sub[j])
{
i++;
j++;
}
else
{
j = next[j];//因为next数组的特性，其中有重复，每次不相等就将j的next数组的坐标重新赋予到j进行比较，
}
}
free(next);
if (j >= sublen)
{
return i- j;
}
else
{
return -1;
}
}
int main()
{
char *str = "ababcabcdabcde";
char *sub = "abcd";
printf("%d\n", KMP(str, sub, 0));
return 0;
}
如果看的似懂非懂，那么我建议去看看大博哥的视频 ，点击：大博哥?，最后感谢大家支持！!? !? !