首先问几个问题？ 我认为只要弄清楚上面的几个问题，KMP算法也就迎刃而解了。 本文就从上面几个问题一个个的铺开 在字符串中有一类问题是从查找子串问题，假如现在有一个主串（较长一些）和一个子串（较短一些）。我想在主串中进行查找，看看主串中是否包含了子串。 比如主串为 aaaab .。子串为aab 。 问主串中是否包含子串？ 答案是显而易见的，主串中包含子串。 这就出现了一种朴素算法，用来查找主串中是否包含子串。 在说朴素算法的实现过程中， 说一个约定：字符串下标都是从0开始的 朴素算法的具体过程： 为什么要有KMP算法？ 答案： 因为上面的对比过程效率比较低，每次对比匹配失败后，i 和 j 都要进行回溯，浪费了好多时间，因此KMP就创造出来了。 首先KMP用代码实现的过程就写了一个while循环，next数组的求解过程也写了一个while循环，就求出来了。没有什么难的地方，重心要放到理解next数组的理解KMP算法过程上。 再说一下朴素算法的大概过程： 拿着子串，一个个的字符和主串进行对比，一旦对比失败，子串后移一个单位，i 和 j 进行回溯（j回溯到0），重新从字串的第一个字符的位置开始对比。 相对于朴素算法，kMP算法的过程是这样的： 拿着子串，一个个的字符去和主串进行对比，一旦对比失败，子串仍然后移（但不一定是一个单位），而且 i 不进行回溯。j 进行回溯，但是并不像朴素算法那样直接j=0，而是回溯到一个其他的地方。（重要！！！） 上面就是KMP算法的大概过程，与朴素算法不一样的地方就是：子串后移的不是一个单位，i不进行回溯，j虽然进行回溯，但并不是回溯到j=0的位置。 对于上面说的，你现在可以不知道子串后移几个单位，j回溯到那个位置，但是你一定要知道KMP的大概过程是啥， 能达到自己不看上面说的，能口述出来的那种（★★★） 下面举两个个例子来说明字符串的前缀和后缀 假如现在有一个字符串为aba。 那么他的前缀字符串（前缀字符串的长度最长要比原字符串少1）分别为：a，ab 他的后缀字符串(后缀字符串的长度最长要比原字符串少1)分别为：a，ba。 再来一个例子abababa。 前缀字符串有：a，ab , aba , abab,ababa,ababab 后缀字符串有：a ，ba , aba , baba,ababa,bababa. 截至到现在：你可以不知道前缀和后缀的作用，但是你一定要会求一个字符串有哪些前缀串和后缀串！！！ 每个字符串（不包括空串）都有自己的前缀串和后缀串，而且每个字符串都有长度，通过对比前缀串和后缀串，我们就能得到一个最大长度，这个长度是指在所有的前缀串中选一个，在所有的后缀串中选一个，而且这俩串相等（可能会有多个相等的串），长度最长。这就被称为最长前缀后缀串。 通过上面一段话，你要会求一个字符串的最长前缀后缀串！！！ 下面说几个例子： 比如上面的字符串aba，他的最长前缀后缀串就是： a 比如上面的字符串abababa,他的最长前缀后缀串就是： ababa 下面说他的作用： 假如现在要在 主串 abababc 中查找 子串 ababc ，如图所示 注意我上面图片的文字。上面的子串为 ababc， 这里咱们把他分成三部分，第一部为为第一个 ab（下标为0和1）。 第二部分为第二个ab（下标为2和3），第三部分为 c（下标为4）。 因为我们在匹配过程中，我们匹配失败，所以要把子串后移，那么后移几个单位合适呢？我们 i 是不进行回溯的（这事KMP的特点，如果你想问 i 不进行回溯，能保证匹配的正确性吗？那就继续看下去吧），j 进行回溯，那么j要回溯几个单位合适呢？ 考虑上面两个问题之前，你要记住咱们有两个已知条件 根据上面的两条结论，我们先看第二个ab（它既是字符串abab的最长前缀后缀，而且他和主串都匹配成功了），通过上面的两个已知条件，你是不是发现了什么联系？ 他们的联系就是：假如我们子串向后移动两个距离，那么字符的第一个ab就和移动之前的第二个ab在主串的对应位置是一样的（主串不会动）。那么这时候子串的第一个位置和第二个位置就不用匹配了，因为之前我们匹配过了，而且匹配的是成功的（利用的等价的关系，一开始字符串的后缀和主串匹配，字符串的后缀和字符串的前缀还相等，那就意味着字符串的前缀和主串对应的位置相等） 截止到现在位置：你应该知道字串的最长前缀后缀是干啥的了，如果你搞懂了上面那个问题，下面的next数据就不然理解了。重要的事情说三遍！！! 一定要搞懂上面那个问题 ！一定要搞懂上面那个问题！一定要搞懂上面那个问题！ 我认为上面那个问题是这篇文章最重要的地方，一定要先去理解他，再继续看下面的！！！ 首先next数组就是和上面的最大前缀后缀对应的，一定要理解上面最大前缀后缀的作用之后，再看下面的next数组的定义 不要仅仅只知道最大前缀后缀的计算过程，一定要理解他的作用所在，不然就不知道为什么我们要引入next数组 next数组定义： 代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀，并且规定next[0]=-1。 举例说明： 字符串abababc（下标从0开始） 那么next[]={-1,0,0,1,2,3,4}; 比如要计算next[1],根据定义可得，他前面的字符串为 a，这个字符串就没有前缀和后缀（前缀和后缀的长度要比原字符串少1）. 比如要计算next[4].它前面的字符串为 abab,最长前缀后缀就是 ab，因此next[4]=2. 上面定义需要注意的地方就是，next[0]=-1,如果计算next [ j ]，那就是看下标 j 前面的所有字符，并不包括下标 j 这个字符。 下面再说说前面两个为解决的问题 这里给出结论，如果匹配失败，j 应该回溯到 next[j] 这个位置 原因：因为在下标j这个位置，他的next[j]代表他的 j 字符之前的字符串最长前缀后缀的大小，那么如果 j 回溯到了next[j]，这个位置，代表他 j 之前的字符仍然不用进行匹配，这就保证了字符匹配的正确性 因为字符 j 回溯了，而且接下来匹配的时候仍然是 i（没变） 和 j（回溯过了） 继续进行匹配，那么子串就要后移，才能在同一条线上继续匹配，当然这个问题在代码中体现不出来，在画图中可以体现出来，下面看图片 如上图所示，i 是不需要进行回溯的，j要进行回溯，回溯到j=next [ j ] 的位置，至于子串的后移操作知识方便理解，在代码中不用体现出来。 这是本篇文章的第五个问题了，你可以先问问自己，前四个问题是否搞清楚了。 这个求解过程，我们来拿例子讲解 比如我们现在有一个字符串 ababcabab 根据next数组的定义，我们手算可以得出next [ ] ={-1,0,0,1,2,0,1,2,3}; 假如我们现在知道了next[0]~next[3]（手算出来的）。想去利用代码去求next [ 4 ]。 那下面我们分析一下怎么求 因为我们已经知道了next[3]=1； 下标3 之前的字符串为 aba,最大前缀后缀为1，就是第一个a（下标为0）和第3个a（下标为2）相等。利用这个已知条件，我们去求解next[4]。 相对于下标3前面的字符串aba，下标4之前的字符串为abab, 在最后多了一个b（下标为3），那么我们可以这样想，因为在next[3]中存在一个最长前缀后缀，那么我们求next[4]是，可以把前面的最长前缀后缀各自再加上一个字符（上面的例子中，aba的前缀是a（下标为0），后缀的为a（下标为2），前缀再加一个字符就是ab（下标为0和1），后缀再加一个字符就是ab（下标为2和3）)。那么我们只需要比较新加的一个字符是否相等是不是就可以了？，这样就分为两种情况 下面我们再看一个新的例子： 字符串为 abaababa 手算可以求得next[]={-1,0,0,1,1,2,3,2}; 假设我们现在已经知道了next[6]=2，我们想用代码的方式根据next[6]求出来next[7]是多少？ 我们再用上面的方法分析一遍，看看怎样根据next[6]求出来next[7]. 下标6前面字符串为abaaba,最大前缀和后缀字符串为 aba，下标为7前面的字符串为abaabab。如果想求下标为7的前面字符串的最大前缀后缀，那就在下标为6的最大前缀后缀后面分别一个字符，那前缀就变成了abaa，后缀变成了abab，通过对比新加的一个字符，发现并不相等，那接下来该怎么办呢？ 我们在重新理一下我们的需求，我们想求next[7],下标为7之前的字符串为abaabab。对比前缀新加的字符a（下标为3）和后缀新加的 b（下标为6）是发现不相等，那么我还是要求最大前缀后缀长，因为前不相等的原因，那这个next[7]肯定不能像相等的情况（next[6]=next[5]+1）来算，所以前缀肯定要缩小（自己可以想想为什么？），这个缩小是指在添加一个新字符的基础上进行缩小。 现在先看几个图片，再继续往下面分析 看完上面图片后，我们开始关注j=3这个下标，我们现在是想在字符串abaa（下标为0-3）中找到一个前缀字符串他等于在我在字符串abab（下标为3-6）中找到一个后缀字符串，而且要长度最大的那种，我们现在还有一个已知条件，那就这字符串abaa和字符串abab的前3个字符是相等的（这是根据next[6]=3推出来的）。 我们现在在讨论一下j=1这个位置，这个因为next[3]=1,假如我们的字符串下标为1的字符和下标为6的字符相等，我们能说这个next[3]+1=2（因为字符串是从下标0开始的）就是这时候的能说这就next[7]的值吗？ 答案是可以 原因：先看next[3]=1.这说明下标3之前的字符串aba的最长前缀后缀为1，就说明下标1之前的字符串和下标3之前的字符串相等，这两个相等的字符串长度为next[3]=1.同时看next[6]=3,这说明下标3之前的字符串和下标6之前字符串相等。根据对称性原理，我们就能说next[3]+1=2就是next[7]的值。 上面说的是相等的情况，如果不相等怎么办，那就继续向前找，假如这里下标为1和下标为6不相等，那下标1就变成next[1]. 按照上面的规律，一直到，知道找到或者找到了头还有找到与之匹配的，那就结束（写代码时控制好边界）。 其实这个一直找的过程就是递归的过程（这地方不太好理解，可以多想想） 下面再看一个网上的图片（图片链接为：点击这里 如果有冒犯版权，我会及时删除 ） 根据上面的过程，我们可以得知如果我们知道了next[0]-next[j-1]。我们就能得出来next[j]（递推求解） 下面具体看代码： 只要求出来next数组，再根据KMP的求解过程，那么KMP用代码实现就很容易得出来了，下面看代码 代码 创作不易，如果您看到了最后，何不点个赞再走呢！！！
引言
一、为什么要有KMP算法？
二、相对于朴素算法，KMP算法有哪些不同？
三、什么是字符串的前缀和后缀，它到底有啥用？
四、KMP算法中的next数组是什么？为什么要用next数组？
五、next数组的求解过程？
//计算next数组函数 void Next(int next[], string s) { int j = 0; int k = -1; int len = s.length(); next[0] = -1;//这个是规定好的 while (j < len-1 ) { if ((k == -1) || (s[k] == s[j])) { k++; j++; next[j] = k; } else { k = next[k];//递归过程 } } }六、KMP算法怎样用代码实现
//KMP搜索 int KMPSearch(string str, string s,int next[]) { int i = 0, j = 0; int strl = str.length(); int sl = s.length(); while (i < strl && j < sl) { if (j == -1 || str[i] == s[j]) { i++; j++; } else { j = next[j];//j回溯的位置，i不进行回溯 } } if (j == sl)//查询到子串s return i - j; else //未查询到 return -1; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
