导航:首页 > 源码编译 > 集合快速匹配字符串算法

集合快速匹配字符串算法

发布时间:2024-11-11 16:56:41

① 图解KMP字符串匹配算法

kmp算法跟之前讲的bm算法思想有一定的相似性。之前提到过,bm算法中有个好后缀的概念,而在kmp中有个好前缀的概念,什么是好前缀,我们先来看下面这个例子。

观察上面这个例子,已经匹配的abcde称为好前缀,a与之后的bcde都不匹配,所以没有必要再比一次,直接滑动到e之后即可。
  那如果前缀中有互相匹配的字符呢?

观察上面这个例子,这个时候如果我们直接滑到好前缀之后,则会过度滑动,错失匹配子串。那我们如何根据好前缀来进行合理滑动?

  其实就是看当前的好前缀的前缀和后缀是否有匹配的,找到最长匹配长度,直接滑动。鉴于不止一次找最长匹配长度,我们完全可以先初始化一个数组,保存在当前好前缀情况下,最长匹配长度是多少,这时候我们的next数组就出来了。

  我们定义一个next数组,表示在当前好前缀下,好前缀的前缀和后缀的最长匹配子串长度,这个最长匹配长度表示这个子串之前已经匹配过匹配了,不需要再次进行匹配,直接从子串的下一个字符开始匹配。

 我们是否每次算next[i]时都需要每一个字符进行匹配,是否可以根据next[i - 1]进行推导以便减少不必要的比较。
  带着这个思路我们来看看下面的步骤:
  假设next[i - 1] = k - 1;
  如果modelStr[k] = modelStr[i] 则next[i]=k

如果modelStr[k] != modelStr[i],我们是否可以直接认定next[i] = next[i - 1]?

通过上面这个例子,我们可以很清晰地看到,next[i]!=next[i-1],那当modelStr[k]!=modelStr[i]时候,我们已知next[0],next[1]…next[i-1],如何推导出next[i]呢?
  假设modelStr[x…i]是前缀后缀能匹配的最长后缀子串,那么最长匹配前缀子串为modelStr[0…i-x]

我们在求这个最长匹配串的时候,他的前面的次长匹配串(不包含当前i的),也就是modelStr[x…i-1]在之前应该是已经求解出来了的,因此我们只需要找到这个某一个已经求解的匹配串,假设前缀子串为modelStr[0…i-x-1],后缀子串为modelStr[x…i-1],且modelStr[i-x] == modelStr[i],这个前缀后缀子串即为次前缀子串,加上当前字符即为最长匹配前缀后缀子串。
代码实现
  首先在kmp算法中最主要的next数组,这个数组标志着截止到当前下标的最长前缀后缀匹配子串字符个数,kmp算法里面,如果某个前缀是好前缀,即与模式串前缀匹配,我们就可以利用一定的技巧不止向前滑动一个字符,具体看前面的讲解。我们提前不知道哪些是好前缀,并且匹配过程不止一次,因此我们在最开始调用一个初始化方法,初始化next数组。
  1.如果上一个字符的最长前缀子串的下一个字符==当前字符,上一个字符的最长前缀子串直接加上当前字符即可
  2.如果不等于,需要找到之前存在的最长前缀子串的下一个字符等于当前子串的,然后设置当前字符子串的最长前缀后缀子串

然后开始利用next数组进行匹配,从第一个字符开始匹配进行匹配,找到第一个不匹配的字符,这时候之前的都是匹配的,接下来先判断是否已经是完全匹配,是直接返回,不是,判断是否第一个就不匹配,是直接往后面匹配。如果有好前缀,这时候就利用到了next数组,通过next数组知道当前可以从哪个开始匹配,之前的都不用进行匹配。

阅读全文

与集合快速匹配字符串算法相关的资料

热点内容
缓存文件写入失败php 浏览:767
服务器pvp和普通有什么区别 浏览:449
机器猫pdf 浏览:845
prototype算法 浏览:715
java进销存系统源码下载 浏览:607
html怎么插入php 浏览:554
疫情期间最佳解压方法 浏览:574
be服务器怎么重装 浏览:346
android微信图文分享 浏览:186
mac桌面怎么显示所有app 浏览:3
linux删除匹配文件 浏览:551
如何在win7中添加服务器 浏览:943
c51单片机原理图 浏览:972
战争之人编辑器的命令 浏览:980
小笼包解压玩具便宜价格 浏览:405
单片机led点阵显示礼花效果 浏览:706
仿陌陌app源码 浏览:261
冰箱压缩机高压管喷油 浏览:250
迅雷下载为什么解压出错 浏览:395
程序员挂毛衣不变形视频 浏览:104