目录
问题引入
BF算法
KMP算法
核心思想
next[j]的规律
next[j]的算法代码解读
KMP算法代码解读
完整代码及其运行结果
next[]算法优化
问题引入
现有两个字符串A、B（假设A是较长的字符串），其长度分别为m，n，请在字符串A中寻找到字符串B的位置，输出B字符串首元素在A字符串中是第几个字符。
BF算法初看这道题目，能想到的最直接最暴力的破解方法就是BF算法，即一个一个试过去，过程大致如下图所示（未具体写出每个元素是什么），A字符串从第一个元素开始，B从首元素开始，每次都和B字符串一个一个元素比过去，对比失败则 A从后一个元素开始，B从其首元素开始，两者再一个元素一个元素进行对比，如果失败A再从后一个元素开始，B又从其首元素开始一个一个元素对比……这样一直到找到B字符串在A里面的位置或者A字符串找完了也未找到才算结束。
#include
int BF(const char* dest, const char* src)
{
int count = 0;
while (*dest != 0 && *src != 0)
{
count++;
char* dtemp = dest;
char* stemp = src;
while (*dest == *src && *dest != '\0') //*dest=0，表示dest字符串比完了，则*src剩余长度无处可比,故应当退出循环
{
dest++;
src++;
if (*src == '\0') //只有*src的所有元素都比完了，*src才=0
return count;
}
dest = dtemp + 1;//指针回溯
src = stemp;//指针回溯
}
return 0;
}
int main()
{
char* a = "abcdefxxx";
char* b = "xxx";
printf("%d\n", BF(a, b));
} BF算法固然可以解决问题，但是每一轮比较之后一直要指针回溯，时间复杂度太高，达到了O(m*n)，于是寻求一种优化的算法，即KMP算法，此种算法可以把时间复杂度降低到O(m+n)，同时需要增加O(n)的空间复杂度，属于是以空间换时间，具体实现如下所示。
KMP算法 核心思想KMP算法的核心思想可以简单概括为：不做无用功。那么何为无用功？试想一下，B字符串本身就是多个元素组成，那么如果B字符串里面有连续多个字符和B字符串首元素的连续多个字符相同，比如"abcueabcdef",后面的abc是和开头三个abc相同的，那么如果本轮对比失败，下一轮对比的时候，A字符串的指针回溯可以不用回溯到本轮对比的下一个，而是回溯到和B字符串的第二个“abc”中的“a”对应的位置，B字符串的指针依然回溯到首元素，如下：
当前面的“abcueabc"都比较过之后，发现i和d不相等，那么此时按照BF算法，应该这样子比，A字符串的指针回溯到本轮第一个比较元素的下一个，即”b“，B字符串的指针回溯到最开始，然后一个一个比：
但是，考虑到A字符串中的一对”abc“相对位置和B字符串中的”ABC“相对位置一摸一样，所以可以考虑，A字符串直接回溯到第2个”abc“的”a“的位置，这样子就避免了第一个”abc“到第二个”abc“之间的比较，并且能明确知道这些比较是无用功，如下图：
在这里，再作出思考，可不可以A字符串的指针不回溯呢？如上图，A字符串的指针本来是在第2个”abc“的后面，即指向“i”，这里不难发现，由于两个指针指向的字符串，前三个是相同的，所以可以直接不用比较，故A字符串的指针不用回溯，B字符串的指针回溯到第一个“abc”的后面一个位置即可。如下图，直接从i和u开始比较就可以了，前面的"abc"不用去管。
以上就是KMP算法的核心思想，举的例子只是众多轮计算中的一轮，KMP算法要进行多轮类似这样的计算。不难发现，A字符串的指针不用回溯，只需要一直指向后一个即可，但是B字符串的指针回溯确是需要技巧，每次回溯的位置都不完全相同，如上图，下一次B字符串的指针应该回溯到第一个位置了。B字符串指针回溯是有规律的，并且每个字符回溯的位置不全相同，所以可以新开一个next[ ]数组来存储其应该回溯到哪一个位置。
next[j]的规律这里先给出数学形式化的描述，如下图，再作详细解读及其原理的解释。
next[j] （j从1开始，并非表示下标，可以理解为第j个字符）就是待匹配串的前j-1个字符构成的的这个子串中，前缀和后缀相等时对应前缀/后缀的最大长度+1。对于前缀和后缀，也不难理解：
前缀：
给定一个字符串“abcd”，其所有前缀：“a”、"ab"、"abc"。这三个，不包括本身。
后缀：
给定一个字符串"abcd"，其所有后缀："d"、”cd"、"bcd"。这三个，也不包括本身。简单地说，前缀就是一个字符串从前往后，后缀就是一个字符串从后往前。
假设有一个字符串“axxunax”，求其前缀和后缀相等时的最大长度。
前缀："a"、“ax"、"axx"、"axxu"、"axxun"、"axxuna"。
后缀："x"、"ax"、"nax"、"unax"、"xunax"、"xxunax"。
不难看出，前缀=后缀是对应前/后缀的最大长度是2。
如果这个字符串再添一个字符成为"axxunaxm"，其next[8]，就是前7个字符构成的子串，即"axxunax"的前缀和后缀相等时对应前/后缀的最大长度+1，即next[8]=3。（j是从1开始。）
比如下图的完整next[j]，所求过程展示：
j=1，按规律next[1]=0。
j=2，前j-1个字符为"a"，无前缀和后缀，属于其他情况，故next[2]=1（next[1]=0,next[2]=1,可直接记成规律）。
j=3，前j-1个字符为"ab",无相等的前后缀，属于其他情况，故next[3]=1。
j=4，j=5，j=6 ，这三个情况和j=3时一样，无相等的前后缀，故next[j]均为1。
j=7，前j-1个字符为"abcuea"，前后缀相等时的最大长度为1，故next[7]=2。
j=8，前j-1个字符为"abcueab"，前后缀相等时的最大长度为2，故next[8]=3。
j=9，前j-1个字符为"abcueabc"，前后缀相等时的最大长度为3，故next[8]=4。
j=10，前j-1个字符为"abcueabcd"，前后缀无相等的情况，故next[10]=1。
j=11和j=10类似，next[11]=1。
了解了next[j]的求法，再和上面KMP算法的核心思想联系起来，不难发现其精妙之处。在这里j=1的时候，next[j]=0是什么原因暂且不讨论，后文会提到，先看其他。当比较到j=2的时候，说明B字符串的第二个元素和A字符串的某个元素在比较，如果不相等，j=next[j]，那么j回溯到了1，即指向“a”,一直到j=6均是如此，因为在B字符串的前j个元素里面，其j-1个元素的前后缀无相等的，那么A、B两个字符串比较到第j个元素时，从核心思想方面来看，B的前j-1个字符的前缀没有能和A字符串中本轮已经比较的元素的后缀相等的，没有能够重叠的内容，故B字符串必须从头开始比较。而到比较到j=7时，如下图所示，假设A字符串中与之对应的元素已经改变，不等于"b"，但是A中元素的改变不影响B字符串，故也就不影响next[7]，比较到当前元素时，发现两者不相等，所以这个时候j=next[j]，B字符串的指针回溯到next[7]=2，即第二个元素，A指针的不回溯，完美符合预期，A和B字符串重叠的“a”不再进行比较，至于之后如何比较下文有详细解答。（也可自行假设验证，j=7时正常，j=8时，A字符串的元素改变……）
next[j]的算法代码解读求得next[j]的代码理解起来着实不容易，下面就是其代码以及详细解读。
void Getnext(int next[],char* t)
{
next[1]=0;
int i=0,j=1;
while(jsize-1的时候，next[T->size]的值已经找到了。
{
if(i==0 || t[j-1] == t[i-1])//这里的i、j对应的是第几个字符，比下标多1，所以比较的时候要-1
{
j++;
i++;
next[j] = i;
}
else i = next[i];//此句时本段代码精华所在
}
}
在这段代码里，传入两个参数，一个是next[]的指针，一个是B字符串的指针t。函数内部设计两个int类型变量i和j，其对应的是B字符串的第几个字符（如下图）。观察整个函数得知，j在设计上是一直++的，不会回溯，所以循环上j每++一次，必定是求得了一个next[j]的值，循环结束就是所有的next[j]都求出来了。
跟着代码走一遍的详细过程：
第1次循环：i=0，j=1，i==0成立，i=1，j=2，next[2]=1。
第2次循环：i=1，j=2，t[i-1] !=t[j-1]，所以i=next[i]=0。
第3次循环：i=0，j=2，i==0成立，i=1，j=3，next[3]=1。
第4次循环：i=1，j=3，t[i-1]=t[j-1]，i=2，j=4，next[4]=2。
第5次循环：i=2，j=4，t[i-1]=t[j-1]，i=3，j=5，next[5]=3。
第6次循环：i=3，j=5，t[i-1]=t[j-1]，i=4，j=6，next[6]=4。
第7次循环：i=4，j=6，t[i-1] != t[j-1]，i=next[i]=2。
第8次循环：i=2，j=6，t[i-1] != t[j-1]，i=next[i]=1。
第9次循环：i=1，j=6，t[i-1] != t[j-1]，i=next[i]=0。
第10次循环：i=0,j=6,i==0成立，i=1，j=7，t[7]=1。
j=7之后就j=strlen(t)，循环结束。
在以上众多次循环中，我们可以发现几个规律：
1、每一次循环的j，求得的其实是next[j+1]，看函数即可知，j先++，然后才求得next[j]，比如第四次循环，一开始j=3，但是最后求得的确实next[4]。
2、next[j] 和next[j+1]的值不会超过1。（原因在下文讲）
3、一开始把i设为0并不影响什么，甚至在以后还有大用，参考第10次循环。
4、求next[j]并不需要知道第j个元素是什么，只需要知道第j-1个元素即可。这个也不难理解，因为上文说过，求next[j]，就是求前j-1个字符构成的的这个子串中，前缀和后缀相等时对应前缀/后缀的最大长度+1。
本段代码精华所在的解释：
如图，假设求一个字符串的next[17]，已知其next[16]是8。（通过上面的循环得出规律，倒推得知next[16]=8这种情况，i=16，j=8，且前面十五个字符串中，有长度为7的前缀和后缀相等(如图中黑色框出)，才满足。）推得i=16，j=8。
然后进入循环判断t[16]和t[8]是否相等，假设不相等，此时i=8，那么i=next[i]，假设next[i]=4的情况，就是说前i-1个字符有长度为3的前缀和后缀相等，如下面第2张图的黄色框出，可是发现框出了第二对相等的黄色框，这是因为，上一段所说，第一张图的两个黑色框的内容完全相等，那么左边的黑色框里有一对黄色框内容相等，无疑，右边的黑色框也有一对黄色框内容相等，并且这两对黄色框的内容完全一样，那么第一个黄色框的内容和第四个黄色框的内容必定也一样，这个时候就很容易理解了，既然此时i前面黄色框内容和j前面黄色框内容一样，那么只需要再判断t[i-1]和t[j-1]是否相同即可，函数中也是这么设计的，相同则……，
不同则此时i=4，假设next[i]=2,那么i=next[i]=2，此时i=2，j=16，由于next[4]=2，那么不难得出，前3个字符串有长度为1的前缀和后缀相等，如下面第3张图图中蓝色框，而上一段得知黄色框内容都相同，那么第四个黄色框也和第一个黄色框一样，对应蓝色框内的内容相等，那么此时只需再判断t[i-1]和t[j-1]是否相同则可……
后面可以参考上面第7、8、9、10次循环，本质上一样。
KMP算法代码解读KMP算法在吃透以上内容之后，其代码并不难理解，代码如下：
int KMP(char* dest,char* src) //dest是指向A字符串，src指向B字符串
{
int next[ssize+1];//ssize表示src指向的字符串的长度,+1是因为第next[0]不使用，用next[1]到next[ssize]
int i=1,j=1;//因为i，j设计的时候就是表示第几个字符，比下标多1，所以初始值直接超前一位
GetNext(next,src); //GetNext()函数和上方一样
while (i<=dsize && j<=ssize)//dsize表示dest指向的字符串长度。这里"="的原因是，dest[i - 1]，如果i=dsize的时候，i-1才是S地址的字符串的最后一位，如果没有=，那么最多比较到倒数第二个字符
{
if (j==0 || dest[i-1]==src[j-1]) //j=0的情况是上一次循环j=next[j]=0,只有j=1才会发生，而src[j-1]显然是第一个字符，这种情况下执行else的话，说明两者此时相对位置的第一个字符就不相等，那么j就得类似于初始那样，j++正好=1初始
{
i++;
j++; //i,j各增1
}
else j=next[j]; //i不变,j后退，现在知道为什么这样让子串回退了吧
}
if (j> ssize)
return i-ssize; //返回匹配模式串的首字符下标
else
return(-1); //返回不匹配标志
}
其主要内容很容易，看while内部，如果j==0或者两个元素相等，j=0的情况下在注释里面有写，两个元素相等，那么指针++，比较后面两个，如果不等，那么j=next[j]，和预期一样。
只有A字符串或者B字符串比较完才会停止循环，这个时候如果j>ssize，只有在循环里面，j=ssize，然后dest[i-1]==src[j-1]，src[j-1]就是src[ssize-1]，ssize-1就是B字符串最后一个元素的下标，这时候相等j才会++，然后大于ssize。B字符串全部比较完了，那么就在A字符串里面找到了B字符串，此时i的位置减去B字符串的长度就是A字符串中和B字符串匹配的首元素的位置。
完整代码及其运行结果#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
void Getnext(int next[], char* t)
{
next[1] = 0;
int i = 0, j = 1;
while (j < strlen(t))
{
if (i == 0 || t[j - 1] == t[i - 1])//这里的i、j对应的是第几个字符，比下标多1，所以比较的时候要-1
{
j++;
i++;
next[j] = i;
}
else i = next[i];//此句时本段代码精华所在
}
}
int KMP(const char* dest, const char* src) //dest是指向A字符串，src指向B字符串
{
//断言
assert(dest);
assert(src);//这两行不影响代码正常运行
int next[11];//ssize表示src指向的字符串的长度
int i = 1, j = 1;//因为i，j设计的时候就是表示第几个字符，比下标多1，所以初始值直接超前一位
Getnext(next, src); //GetNext()函数和上方一样
while (i <= strlen(dest) && j <= strlen(src))//dsize表示dest指向的字符串长度。这里"="的原因是，dest[i - 1]，如果i=dsize的时候，i-1才是S地址的字符串的最后一位，如果没有=，那么最多比较到倒数第二个字符
{
if (j == 0 || dest[i - 1] == src[j - 1]) //j=0的情况是上一次循环j=next[j]=0,只有j=1才会发生，而src[j-1]显然是第一个字符，这种情况下执行else的话，说明两者此时相对位置的第一个字符就不相等，那么j就得类似于初始那样，j++正好=1初始
{
i++;
j++; //i,j各增1
}
else j = next[j]; //i不变,j后退，现在知道为什么这样让子串回退了吧
}
if (j > strlen(src))
return i - strlen(src); //返回匹配模式串的首字符下标
else
return -1; //返回不匹配标志
}
int main()
{
char arr1[] = "abcxusingnamexforwhile";
char arr2[] = "usingnamex";
printf("%d", KMP(arr1, arr2));
return 0;
} 得到的结果是5，表示arr1中的arr2字符串的首元素在arr1字符串中是第5个字符。
next[]算法优化KMP算法已经如此强大，可是还能再次优化，其主要就是对next[]进行优化。
比如：
主串s=“aaaaabaaaaac”
子串t= “aaaaac”这个字符串里面两个红色字符比较的时候，不相等，那么如下图所示，经历了如下六步，但是这几步本就可以省略，完全没有必要把“b”和一个个“a”进行对比，因为在t字符串的“aaaaa”里面，next[j]回溯之后指向的字符都一样，都是“a”,原字符和“b”不匹配，回溯之后指向的字符和原字符一样，同样也不可能和“b”匹配，但是这里却要一个一个试过去，这就是这种情况下KMP算法的劣势。
我们改进后的next数组命名为：nextval数组。
KMP算法的改进可以简述为： 如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next值。
举例：
1.第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为1。
2.第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则第三位的nextval值为第一位的next值，为0。
3.第四位的next值为2，那么将第四位和第二位进行比较，不同，则第四位的nextval值为其next值，为2。
4.第五位的next值为2，那么将第五位和第二位进行比较，相同，第二位的next值为1，则继续将第二位与第一位进行比较，不同，则第五位的nextval值为第二位的next值，为1。
5.第六位的next值为3，那么将第六位和第三位进行比较，不同，则第六位的nextval值为其next值，为3。
6.第七位的next值为1，那么将第七位和第一位进行比较，相同，则第七位的nextval值为O7.第八位的next值为2，那么将第八位和第二位进行比较，不同，则第八位的nextval值为真—next值，为2。
代码如下：
void Getnextval(int nextval[],char* t)
{
nextval[1]=0;
int i=0,j=1;
while(j个人对于KMP算法的全部理解就是如此，经过两天的不懈努力终于完成里第一篇近万字的博客！！！如果觉得本篇对你理解KMP算法有帮助，可以点赞+关注（嘿嘿），后续关于数据结构也会写，因为KMP算法本身就是接触到数据结构里面的串才有所了解。
最后的最后，谢谢各位看完本文！！！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）