【未来虫教育】字符串匹配之KMP算法与BF算法

(一) 字符串匹配，从 主串 中匹配目标串，如果在主串中匹配到，就返回与目标串相匹配的对应主串的第一个字符·
(二)
（1） BF算法， 即暴力(Brute Force)算法 ，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。
缺点： 时间复杂度较大0（mn）(最坏的情况下)（ m为主串长度，n为目标串长度 ）
BF算法演示过程：

（2） KMP算法： 是一种 改进的字符串匹配算法, 由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是 利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配 的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息 。 K MP算法的
时间复杂度
O(m+n)
为什么要求next数组,next数组指的是什么？
KMP的next数组简单来说，假设有两个字符串，一个是待匹配的字符串S1,一个是要查找的关键字S2。现在我们要在S1中去查找是否包含S2，用 “i” 来表示S1遍历到了哪个字符， KMP就是保证 i 永远不回退，只回退 j 来使得匹配效率有所提升。它用的方法就是利用 strKey在失配的j为之前的成功匹配的子串的特征来寻找j应该回退的位置 。
前缀和后缀
"前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

nextval是为了弥补next缺陷所产生的
实例如下：
主串为“aaabaaaab”、模式串为“aaaab”那么，比较的时候就会发生一些浪费的情况：比较到主串以及模式串的第四位时，发现其值并不相等，据我们观察，我们可以直接从主串的第五位开始与模式串进行比较，而事实上，却进行了几次多余的比较。使用nextval可以去除那些不必要的比较次数。
KMP算法要解决的问题就是 在字符串（也叫主串）中的模式（pattern）定位问题。 说简单点就是我们平时常说的关键字搜索。模式串就是关键字（接下来称它为P），如果它在一个主串（接下来称为T）中出现，就返回它的具体位置，否则返回-1（常用手段）。

具体解释：
首先，对于这个问题有一个很单纯的想法：从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。这有什么难的？
我们可以这样初始化：
之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动，如果不一致，如下图：
A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后又重新开始这个步骤：

#include

#include

#include

int BFindex(char S[],char T[],int pos)//BF算法匹配字符串{int i=pos;int j=1;int length1=strlen(S);int length2=strlen(T);while((i<=length1)&&(j<=length2))//两个字符串均为比较到串尾（只有有一个到串尾就跳出循环）{ if(S[i]==T[j-1]) { i++;j++; } else { i=i-j+2; j=1; }}if(j>length2){ return i-length2+1;}else{return 0;printf("匹配失败!");}}int Index_KMP(char S[],char T[],int next[],int pos)//字符串匹配{int i=pos;int j=1;int length1=strlen(S);int length2=strlen(T);while(i<=length1&&j<=length2) //两个字符串均为比较到串尾（只有有一个到串尾就跳出循环）{ if(j==0||S[i]==T[j-1]){++i;++j;} //匹配进行中 else{ j=next[j];} //移动字符串}if(j>length2)return i-length2+1;else{ return 0;printf("匹配失败！");}}void get_next(char T[],int next[]) //获取next的值{int i=1;next[0]=0;int j=0;int length3;length3=strlen(T);while(i