PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(七)——串与实现KMP算法

(原创内容,转载请注明来源,谢谢)

一、定义

串是0个或多个字符组成的有限序列,任意连续字符组成的子序列称为子串,与其对应的序列称为主串。子串在主串的第一个位置称为串的位置。当长度相等且每个字符对应相等的两个串,称为其相等。

二、串的表示方式

2.1 定长顺序存储方式

该存储方式类似线性表的顺序存储。有两种存储方式,一种是以下标为0开始的数组存储每个字符,另一种是以“\0”作为结尾。当长度超过定长时,超出部分会被截取。

2.2 堆分配存储表示

和定长的存储方式相同,区别在于存储空间是动态分配的,因此如果超长不会被截取,而是会重新分配存储空间。

2.3 块链存储表示

类似链表形式。但是每个节点不一定只存一个字符,也可以设置每个节点存多个字符,这样存储密度降低,会节约空间。(因为链表自身还带有头指针,因此越多的节点需要越多的空间分配给头指针。)

存储密度=串所占的存储值/实际分配的存储值。密度越小处理起来越方便(极端情况就是每个节点存储一个字符,这样增删改字符都很方便),但是占用的存储空间大。

三、串的模式匹配算法

求子串在主串中的位置的算法称为模式匹配算法。分为常规方法与KMP方法。

3.1 常规方法

当主串的字符数量不大,或者主串与子串的长度相差很小时,可以采用此方法。

这个方法的思想是:从主串的第一个位置开始,比较主串与模式串的每个字符,若匹配成功,则返回当前模式串所在的主串的第一个字符,作为模式串在主串种的位置;若匹配失败,则从主串的第二个位置开始,与模式串的第一个字符进行比较。以此类推。

该算法的时间复杂度是O(M*N),M、N是主串、模式串的长度。当主串比子串常非常多,或者一些特定情况下(例如主串是0000000000000000000000001,匹配的模式串是0000000001),该方法将要进行大量的运算,速度较慢。

PHP源码如下:

<?php
function getSubString($mainStr, $suStr){
         $i= 0;
         $j= 0;
         while($j<strlen($suStr)&& $i<strlen($mainStr)){
                   if(!isset($mainStr[$i])){
                            break;
                   }
                   if($mainStr[$i++]==$suStr[$j++]){
                   }else{
                            $i= $i - $j +1;
                            $j = 0;
                   }
         }
         if(strlen($suStr)== $j){
                   return$i-$j;
         }else{
                   return-1;
         }
}
$mainStr = 'abbcabcbca';
$suStr  =   'cabcbca';
$suStr2 =   'bcbb';
echo getSubString($mainStr, $suStr);//运行结果为3,即第四个位置开始匹配
echo getSubString($mainStr, $suStr2);//运行结果为-1,即不匹配

3.2 KMP算法

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。

KMP算法的关键是利用匹配失败后的信息,以及已经匹配成功的前置信息,尽量避免主串重新从第二个字符开始匹配,以减少模式串与主串的匹配次数以达到快速匹配的目的。

具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n),m、n是模式串、子串的长度。

KMP主要推理过程:

1. 假设主串长度mainLength,模式串长度subLength,模式串处于主串的位置curPosition,当前已经匹配的模式串长度为matchedLength,模式串已匹配的字符串的最大相同前后缀的值为maxSameSuffixLength(此概念下面会介绍),此时出现下一个字符不匹配的情况。

2. 模式串在最极端的情况下,每个字符都不一样,此时由于前面matchedLength的字符都已经完成匹配,区间[curPosition, curPosition+matchedLength-1 ]内肯定不会再出现与模式串匹配的情况,因此则可以将模式串从curPosition位置移到curPosition+matchedLength位置。

3. 但是,当模式串不处于极端情况,则已经匹配的字符中,可能存在相同的数个字符,一次性位移那么多字符有可能遗漏比较内容。此时需要引入前缀和后缀的概念。

小编笔名linhxx,前缀是l、li、lin、linh、linhx,后缀是inhxx、nhxx、hxx、xx、x。当前缀与后缀中存在相同的长度,如abcabc,此串相同前缀和后缀相同的长度为3(即前缀的abc和作为后缀的abc)。

4、为了保证从前缀与后缀相同的地方开始,主串后面的位置的尝试匹配不被遗漏,因此,模式串第一位需要位移的长度是matchedLength-next[matchedLength-1],并且接下来的匹配比较从子串的第next[matchedLength-1]位开始。

5、相同前后缀(next函数)的程序求解方法:

模式串第k位的相同前后串长度最大值用next[k]表示。

求解条件一:根据next定义,易知next[0]=0。因此需要求的next[k]的k取值范围是1至strlen(模式串)-1(减一是考虑到数组下标的问题)。

求解条件二:当第k-1位的next为0,即next[k-1]=0,只需要比较模式串第k个字符与第1个字符是否相同,是则next[k]=1,否则为0。

求解条件三:当第k-1位的next不为0,且模式串的第k位与模式串的第next[k-1]位相同时,next[k]= next[k-1]+1。

求解条件四:当第k-1位的next不为0,且模式串的第k位与模式串的第next[k-1]位不相同时,把字符串的前next[k-1]位与第k位拼接后,迭代求子next函数,则子next函数的最后一个值即为需求的值。

代码运行结果如下:

PHP源码如下:

<?php
//获取next的方法
//输入:$str 需要匹配的模式串
functiongetNext($str){
         $next = array();
         //第一个字符的next值是0
         $next[0] = 0;
         $strLen = strlen($str);
         //从第二个字符开始计算next的值
         for($k=1;$k<$strLen;$k++){
                   //当第k个字符的前一个字符next值是0时,
                   //只需要比较第k个字符与第一个字符是否相同即可
                   if($next[$k-1]==0){
                            $next[$k] =($str[$k]==$str[0] ? 1 : 0);
                   }else{//第k个字符的前一个字符不是0
                            //$next[$k-1]表示第k-1个字符的匹配的值,当第k个值与第$next[$k-1]+1个值一样时,$next[$k]= $next[$k-1] +1
                            //由于数组下标-1的关系,第$next[$k-1]+1个值表示为$str[$next[$k-1]]
                            if($str[$k] ==$str[$next[$k-1]]){
                                     $next[$k] =$next[$k-1] +1;
                            }else{
                                     //当第k个值与第$next[$k-1]+1个值不一样时
                                     //把$k-1位置已经匹配的字符数量$next[$k-1]与第k个字符拼接成子字符串,并递归调用求该子字符串的next值(即求内部的对称)
                                     $smallStr =substr($str, 0 , $next[$k-1]);
                                     $smallStr.= $str[$k];
                                     $arrSmallNext= getNext($smallStr);
                                     //求得的子串最后一个字符即刚刚拼接上去的需要求next的字符,该值即为next的值
                                     $next[$k] =$arrSmallNext[strLen($smallStr)-1];
                            }
                   }
         }
         return $next;
}
//KMP算法
functionkmp($mainStr, $suStr){
         $next = getNext($suStr);//用子串构造next
         $mainLen = strlen($mainStr);
         $suLen = strlen($suStr);
         $result = -1;
         for($i=0;$i<$mainLen;){
                   for($j=0;$j<$suLen;){
                            //如果匹配则继续匹配下一个字符
                            if($mainStr[$i]==$suStr[$j]){
                                     $i++;
                                     $j++;
                                     if($i >=$mainLen){
                                               break;
                                     }                                   
                                     continue;
                            }
                            //不匹配的情况
                            //第一位就不匹配,则直接退出循环,比较下一个字符
                            if($j==0){
                                     $i++;
                                     $j=0;
                                     //若i超出范围,退出循环
                                     if($i >=$mainLen){
                                               break;
                                     }                                   
                                     continue;
                            }
                            //第j位不匹配,前面大串已经位移了j位
                            //$i = $i -$next[$j-1];//括号内为位移长度,再加上$next[$j-1]是为了让字符串从此位开始比较
                            $j = $next[$j-1];//模式串下一次开始的也是从此位置开始
                            if($i >=$mainLen){
                                     break;
                            }
                   }
                   //如果j和模式串长度相同,说明顺利比完每一个模式串字符,则返回模式串在大字符串中的首字符位置
                   if($j == $suLen){
                            $result = $i - $j;
                            break;
                   }
         }
         return $result;
}
$mainStr ='abcbcacchhycbcabcbcab';
$suStr   =   'bcbcab';
$suStr2  =  'bcbb';
echo '<br/>kmp求bcbcab在abcbcacchhycbcabcbcab位置:' . kmp($mainStr, $suStr);
echo '<br/>kmp求bcbb在abcbcacchhycbcabcbcab位置:' . kmp($mainStr, $suStr2);

Kmp算法仍有相关的改进算法,可以进一步加快检索速度,今后的算法专题中会有专门的描述。

——written by linhxx 2017.07.05

相关阅读:

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - Category的本质

iOS底层原理总结 - Category的本质 面试题 Category的实现原理,以及Category为什么只能加方法不能加属性。 Category中有loa...

3316
来自专栏java学习

面试题34(关于接口的理解?)

对接口的描述正确的是? A 一个类可以实现多个接口 B 接口可以有非静态的成员变量 C 接口可以实现方法 D 实现接口的任何类,都需要实现接口的方法 考点:考察...

3186
来自专栏King_3的技术专栏

leetcode-674-Longest Continuous Increasing Subsequence

1895
来自专栏软件开发 -- 分享 互助 成长

C++STL 之排列

固然我们可以自己使用递归编写全排列程序,但是既然STL里面已将有了这个功能为什么不直接用呢,下面就写一下直接使用C++ STL生成全排序的程序 函数名:next...

1937
来自专栏一个会写诗的程序员的博客

第6章 扩展函数与属性第6章 扩展函数与属性

在使用Java的时候,我们经常使用诸如StringUtil, DateUtil等等一堆工具类,代码写起来也比较冗长。举个例子,获取一个字符串的第一个字符值、最后...

562
来自专栏Android机器圈

数据结构----线性表顺序和链式结构的使用(c)

PS:在学习数据结构之前,我相信很多博友也都学习过一些语言,比如说java,c语言,c++,web等,我们之前用的一些方法大都是封装好的,就java而言,里面使...

633
来自专栏决胜机器学习

PHP数据结构(二十三) ——快速排序

PHP数据结构(二十三)——选择排序 (原创内容,转载请注明来源,谢谢) 一、概述 选择排序的基本思想,是每一趟在n-i+1(i=1,2…n-1)个记录中选...

3528
来自专栏小勇DW3

LinkedHashMap 源码分析

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

1183
来自专栏待你如初见

Day01

不推荐使用强制的类型转换,它容易丢失数据,除非不得已,并且你确定不会出现数据丢失才可以使用。

1395
来自专栏面朝大海春暖花开

入住腾讯云+社区

对于的github基础代码https://github.com/chywx/JavaSE

991

扫码关注云+社区