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 条评论
登录 后参与评论

相关文章

来自专栏我是攻城师

在Scala里面如何使用元组

3344
来自专栏Golang语言社区

golang错题集

为什么呢?是不是有点诧异? 输出的都是“annei”,而“annei”又是“names”的最后一个元素,那么也就是说程序打印出了最后一个元素的值,而name对于...

960
来自专栏从流域到海域

《Java程序设计基础》 第6章手记

本章主要内容: - 类的定义 - 成员变量和成员方法 - 类及成员的修饰符 - 对象的创建与使用 - 成员变量的访问与方法的...

1805
来自专栏有趣的Python

算法与数据结构(二):排序篇-O(n^2)算法:选择 & 插入算法优化排序基础

排序基础 O(n^2)的算法虽然简单,但也实用!让我们从最简单的基础排序算法开始,打开我们的算法大门! 排序算法 O(n^2)的排序算法 最优的时间复杂度为O...

2964
来自专栏向治洪

Kotlin语法基础之运算符

运算符 计算机程序中最小的程序单位成为表达式,每个表达式都可以由两部分组成,即操作数和运算符。操作数可以是变量、常量、类、数组、方法等,甚至是其他表达式。而运算...

1925
来自专栏逆向技术

逆向知识第七讲,三目运算符在汇编中的表现形式,以及编译器优化方式

                  逆向知识第七讲,三目运算符在汇编中的表现形式 一丶编译器优化方式 首先说一下编译器优化方式. 1.常量折叠 2.常量传播 3...

1718
来自专栏前端知识分享

第195天:js---函数对象详解(call、apply)

683
来自专栏Linyb极客之路

简洁又快速地处理集合——Java8 Stream(下)

而 parallelStream() 是并行流方法,能够让数据集执行并行操作,后面会更详细地讲解

1002
来自专栏IT可乐

Java数据结构和算法(十三)——哈希表

  Hash表也称散列表,也有直接译作哈希表,Hash表是一种根据关键字值(key - value)而直接进行访问的数据结构。它基于数组,通过把关键字映射到数组...

2518
来自专栏小二的折腾日记

牛客网-剑指offer-10

主要是想为什么会有最大的和,一个情况是,新加上的数比原来的数都要大,就要开始考虑需不需要原来的数了。所以我们需要两个数,一个保存最大的和,用来返回,一个 保存当...

573

扫描关注云+社区