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