c++ KMP子串查找算法怎么用

这篇文章主要介绍了c++ KMP子串查找算法怎么用的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇c++ KMP子串查找算法怎么用文章都会有所收获，下面我们一起来看看吧。我们在之前学习了字符串类，那么查找字符串类的需求就随之而来。如何在目标字符串 S 中，查找是否存在子串 P？我们大家最先能想到的肯定是朴素解法，何谓朴素解法呢？就是一个一个进行对比，如果比对不成功，便向后移一位。代码如下那么此时的解法肯定不太好，因为它的时间复杂度为 O(m*n)。那么我们该如何对其进行优化呢？我们来看看下图由上图我们可以得出一个结论：因为 Pa ！=Pb 且 Pb == Sb；所以 Pa！+ Sb；因此，子串 p 右移 1 位是没有意义的。接下来我们以示例字符串为例来进行分析说明，如下我们看到在第一步的时候，第 1 个字符就匹配失败，然后我们直接右移 1 位；直至第 7 个字符匹配失败，此时我们通过肉眼观察可知，右移 4 位是最好的；接下来在匹配到第 3 个字符的时候又失败了，通过肉眼观察可知，右移 2 为是最好的；后面以此类推。那么我们是否有什么发现呢？只要我们能知道需要右移几位，我们便可以轻易的得出结论。那么这块就有前人已经发现了开发云主机域名规律，我们只需掌握这个方法即可轻易的解决问题。那么伟大的发现是什么呢？在匹配失败时的右移位数与子串本身相关与目标串无关；移动位数 = 已匹配的字符数 – 对应的部分匹配值；任意子串都存在一个唯一的部分匹配表。下来我们来看看一个部分匹配表的示例，如下那么问题来了，这个部分匹配表是如何得到的呢？首先我们来介绍两个概念：前缀和后缀。前缀是指除了最后一个字符以外，一个字符串的全部头部组合；后缀是指除了第一个字符以外，一个字符串的全部尾部组合。那么部分匹配值便是前缀和后缀最长共有元素的长度，我们以字符串 “ABCDABD” 为例来进行分析，如下图所示我们看到在第一个字符 A 的时候，它的交集为空，因此匹配值为 0；在前两个字符时，同样为空，因此匹配值也为空；直至第5个字符时，交集为 A，因此它的匹配值为 1；第 6 个字符时，交集为 AB，因此此时的匹配值为 2；最后一个字符时，交集为空，因此匹配值为 0。那么我们知道了如何手动的求解部分匹配值，那么如何在程序中编程产生部分匹配表呢？实现关键：1、PMMT[1] = 0（下标为 0 的元素匹配值为 0）2、从 2 个字符开始递推（从下标为 1 的字符开始递推）3、假设 PMT[n] = PMT[n-1] + 1（最长共有元素的长度）4、当假设不成立，PMT[n] 在 PMT[n-1] 的基础上减小下来我们来实现部分匹配表的程序，代码如下我们来看看结果是否和我们上面推导的是一样的？我们看到结果是 0 0 0 0 1 2 0，和我们上面手动推导出来的结果是一致的，因此这个部分匹配表的代码编写是正确的。下来我们就来看看部分匹配表的使用（KMP 算法）：下标 j 处匹配失败 –> 前 j 位匹配成功 –> 查表 PMT[j-1] –> 右移位数 j-PMT[j-1]。如下图所示因为 s[i] != p[j]， 所以查表可知，LL= PMT[j-1]。于是乎，右移，i 的值不变，j 的值改变，j = j – (j-LL) = LL = PMT[j-1]。下来我们来看看 KMP 子串查找算法的具体实现，如下我们来看看结果，如下关于“c++ KMP子串查找算法怎么用”这篇文章的内容就介绍到这里，感谢各位的阅读！相信大家对“c++ KMP子串查找算法怎么用”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注开发云行业资讯频道。

相关推荐: phpstudy composer怎样安装及使用

这篇文章给大家分享的是有关phpstudy c开发云主机域名omposer怎样安装及使用的内容。小编觉得挺实用的，因此分享给大家做个参考。一起跟随小编过来看看吧。本人是windows 系统phpstudy 是最新2018版本以安装laravel框架为例子一如图…