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

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

发表于

我来说两句

1 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

C/C++中对链表操作的理解&&实例分析

链表概述    链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量,以head表示,它存放...

3044
来自专栏梧雨北辰的开发录

Python学习(5):基本数据类型之Number

1428
来自专栏向治洪

Kotlin语法基础之控制流

Kotlin 的控制流与 Java 的控制流基本相同,只是使用 when 代替了 switch。当然,在 Kotlin中,if 和 when 不仅仅可以作为语句...

1817
来自专栏前端知识分享

第199天:js---扩充内置对象功能总结

582
来自专栏小樱的经验随笔

KMP算法学习(详解)

kmp算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。不过由于其难以理解,所以在很长的一段时间内一直没有搞懂。虽然网上有很多资料,但是鲜见好的博客能简...

2575
来自专栏算法与数据结构

PTA 7-1 有序链表的插入(20 分)

已知一个递增有序链表L(带头结点,元素为整数),编写程序将一个新整数插入到L中,并保持L的有序性。 其中单链表的类型定义参考如下: typedef int el...

2618
来自专栏wOw的Android小站

[CS]聊聊字符编码

用爬虫在百度爬图片的时候,发现部分查询关键字的时候,出现爬不出图片的情况.比如在爬鱼的时候,就没有结果.爬鱼 图片就会有结果.

452
来自专栏codingforever

经典算法巡礼(二) -- 排序之选择排序

选择排序,如冒泡排序一样,从名字中即可大概猜测其排序的原理。其工作原理就是从未排序的数组中选出最大(小)的元素,将其放置至数组的首(尾)部,重复此过程直至没有未...

231
来自专栏calmound

sscanf

sscanf与scanf类似,都是用于输入的,只是后者以键盘(stdin)为输入源,前者以固定字符串为输入源。    第一个参数可以是一个或多个 {%[*]...

3386
来自专栏云瓣

正则&highlight高亮实现(干货)

写完正则表达式以后在浏览器上检测实在是不方便,于是就写了一个JS正则小工具,大大地提高了学习效率。学习之余用正则实现了一个highlight高亮demo,欢迎交...

33012

扫码关注云+社区