九分钟带你弄懂KMP算法【原理篇】-创新互联
前言：
创新互联是一家专注于网站制作、做网站与策划设计,覃塘网站建设哪家好?创新互联做网站,专注于网站建设10余年,网设计领域的专业建站公司;建站业务涵盖:覃塘等地区。覃塘做网站价格咨询:18980820575在一些寻找子串的问题中，我们常常使用的是BF算法，也就是暴力算法，这样做的时间复杂度通常都是O(N^2)，且不能体现出算法的美妙之处（虐人之处），于是三位大佬D.E.Knuth，J.H.Morris和V.R.Pratt提出了一种船新的方法，时间复杂度真的很低 O(n+m),这个算法由三位大牛的名字首字母来命名，也就是我们今天的主角KMP算法。
我将KMP算法的详解分为三个篇章：
->【原理篇】：主要讲解KMP实现的原理，以及手动求NEXT数组。
【数理篇】：主要讲解如何在手动求出NEXT数组的情况下，找出数学规律，为之后的算法实现奠定基础。
【实现篇】：主要讲解以C语言代码的方式实现KMP算法，以及NEXT数组的优化。
其余篇章将在之后更新
实现原理：🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈
制作不易，若对你有帮助的话点赞、关注、评论走一波，你们的支持是我前进路上大的动力。
当你有两个字符串DES（目标字符串）和PAT（模板字符串），你要去DES中寻找是否有子字符串与模板串PAT相同。
BF也就是暴力算法的实现思路是这样的：当DES[i]==PAT[j]的时候，先记录此时的I下标，令cnt=I,之后执行I++，J++。若DES[i]!=PAT[j]的时候I回退到起始下标，也就是cnt的位置，j回退到PAT字符串的首位也就A(0)的位置；
聪明的你一定发现，这样做会导致i和j一直往回走，效率实在不高，有没有可能让j有规律的回退，而i一直向前呢？
KMP算法就是这样做的！试想一下，当i与j分别指向这的时候，表示前三个字符都匹配上了，接下来我们按照BF算法的思路，让i，j向后移动一格。
这时候DES[i]所指向的字符为A，而PAT[j]所指向的字符为C，按照BF的思路，此时i j都需要执行一个回退的操作。但你们仔细观察看看，j能指向C是否能说明，前三个元素AAA是DES中前四个元素的一个子串？
也就是说PAT的AAA一定在DES中能被匹配上，不然J也无法移动到这了。
那我们这时候还需要将J回退到最开始的位置吗？我们不需要了！我们只需要将j移动到PAT数组中，以PAT[0]为首，PAT[j-1]为结尾的两个子字符串的长度位就可以了。听不懂没关系，底下我会介绍这种算法
（例如AAA，以第一个A为首，中间的A为尾是第一个子字符串，以中间的A为首，最后一个A为尾是第二个子字符串，这两个子字符串的长度为2，2为长度位，这时将J移动到PAT中下标为2的地方）。
NEXT数组：但你不禁会想：为什么要这么退呢？因为你退回的是DES中匹配过的所有的字符的子字符串。这是一个难点，可以自己多举几个例子想想。若没听懂也可以先接着往下看，影响不大。
这也就是KMP算法当中的核心之处：NEXT数组。
在前面，我们已经简单体会到了NEXT数组，可以用这么一句话来概括NEXT数组的作用
指导PAT中的j要回退到PAT中的哪一个位置。NEXT[j]存储了从PAT[0]到PAT[j-1]位置，以PAT[0]为首，PAT[j-1]为结尾的两个最长子字符串的长度位（可以重叠，但不能相等）。
那么我们怎么来求NEXT数组呢？别急，接下来我会举两个例子。
EX1：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| PAT字符串 | a | b | c | a | b | a | b | c | a | b | c |
| NEXT数组 | -1 | 0 | 0 | 0 | 1 | 2 | 1 | 2 | 3 | 4 | 5 |
我们规定，NEXT[0]=-1 NEXT[1]=0.(有些地方的定义不一样，但这没关系，在代码中做相应修改就可以了)从NEXT[2]开始，我们需要自己算。
牢记我们的口诀，NEXT[j]=以PAT[0]为首，PAT[j-1]为结尾的两个最长子字符串的长度位（可以重叠，但不能相等）。
我们看看NEXT[2]中是否满足呢，首：a 尾：b显然没有以a为首b为尾的字符串，那么我们就在这里填上0，也就是NEXT[2]=0；
NEXT[3]：首：a 尾：c，显然也没有以a为首，c为尾的两个子字符串，所以NEXT[3]=0;
NEXT[4]：首：a 尾：a，pat[0]=a,pat[3]=a，找到了两个子字符串（就是首尾本身），他们有多长呢？显然是长度1，所以NEXT[4]=1；
NEXT[5]：首：a 尾：b，pat[0-1]=ab,pat[3-4]=ab（这里表示下标3到下标4，下同），找到了两个子字符串，以PAT[0]为首，PAT[4（5-1）]为尾的两个字符串，长度为2，所以NEXT[5]=2；
NEXT[6]：首：a 尾：a，pat[0]=a,pat[5]=a，找到了两个字符串（就是首尾本身），他们有多长呢？显然是长度1，所以NEXT[6]=1；
NEXT[7]：首：a 尾：b，pat[0-1]=ab,pat[5-6]=ab，找到了两个子字符串，以PAT[0]为首，PAT[6（7-1）]为尾的两个字符串，长度为2，所以NEXT[7]=2；
NEXT[8]：首：a 尾：c，pat[0-2]=abc,pat[5-7]=abc，找到了两个子字符串，以PAT[0]为首，PAT[7（8-1）]为尾的两个字符串，长度为3，所以NEXT[8]=3；
NEXT[9]：首：a 尾：a，pat[0-3]=abca,pat[5-8]=abca，找到了两个子字符串，以PAT[0]为首，PAT[8（9-1）]为尾的两个字符串，长度为4，所以NEXT[9]=4；
NEXT[10]：首：a 尾：b，pat[0-4]=abcab,pat[5-9]=abcab，找到了两个子字符串，以PAT[0]为首，PAT[9（10-1）]为尾的两个字符串，长度为5，所以NEXT[10]=5；
到此，该PAT的next数组已经告一段落。下面还有一个例子，我直接给出了答案，若还是没懂，可以对照上面的方法进行求解或评论私信问我都可。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| PAT数组 | a | b | c | a | b | a | b | c | a | b | c |
| NEXT数组 | -1 | 0 | 0 | 0 | 1 | 2 | 1 | 2 | 3 | 4 | 5 |
至此，本篇博客的内容九分钟带你弄懂KMP算法【原理篇】告一段落，若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上大的动力。
若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
诸君，山顶见！
🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享名称：九分钟带你弄懂KMP算法【原理篇】-创新互联
当前URL：http://mswzjz.cn/article/dhgpse.html