数据结构-BF算法及KMP算法

jollywing 发布于2019-06-27 16:20 / 2441人阅读

摘要：算法代码复杂度最坏情况的时间复杂度。算法简单记忆分为两步模式串扫描，生成数组，。算法对算法的回溯问题进行了改进，在整个匹配过程中对主串仅需从头至尾扫描一遍。在定义函数时在参数前加上改为引传递。一般情况为值传递，对象除外。

BF算法 代码

= strlen($t)) $k = $i - strlen($t);
    else $k = -1;
    return $k;    
}
$str1 = "abaabcabclkjlkff";
$str2 = "abc";
echo bf($str1,$str2);
?>

复杂度

最坏情况的时间复杂度O(m*n)。m为模式串长度。n为目标串长度。

KMP算法 代码

=strlen($t)) $v = $i - strlen($t);
    else $v = -1;
    return $v;
}

$s="ababcabcacbab";
$t="abcac";
$k;
$k = KMPIndex($s,$t);
echo $k;
?>

时间复杂度

时间复杂度为O(m+n)。m为模式串长度。n为目标串长度。
算法简单记忆分为两步:1.模式串扫描，生成next数组，O(m)。2.主串扫描，匹配，O(n)。
KMP算法对BF算法的回溯问题进行了改进，在整个匹配过程中对主串仅需从头至尾扫描一遍。

其他

php函数参数传递。在定义函数时在参数前加上"&"改为引传递。一般情况为值传递，对象除外。

php在字符串索引某个字符。若包含中文字符需要另行处理。js可以通过"[]"直接索引。java用charat函数。

BM算法。

思考

看一个生成next数组的简单例子。
考虑模式串t="abab",观察一下next数组的生成过程。

初始化。j=0 k=-1 next[0]=-1

第一趟。j=1 k=0 next[1]=0

第二趟。k=next[0]=-1

第三趟。j=2 k=0 next[2]=0

第四趟。匹配。j=3 k=1 next[3]=1

第五趟。匹配。j=4 k=2 next[4]=2

这里首先可以注意到在第六步中j=4，而实际在我们的模式串"abab"中4这个下标已经越界了，嗯嗯，不要着急，我们先来看看在每一趟循环中到底做了什么。

        if($k==-1||$t[$j] == $t[$k]){
            $j++;
            $k++;
            $next[$j]=$k;
        }
        else $k = $next[$k];

代码不过5行，一个if...else...的判断语句。假设看的同学已经在其他地方看过这里前后缀的原理了。
如果k=-1或t[j]=t[k],j++,k++,next[j]=k。
这里的k=-1暂时不考虑他的作用，那么就是如果主串（模式串）与子串中的字符匹配，则主串指针向后一位，子串指针向后一位，给next数组赋值。
否则k=next[k]。否则向前移动子串指针。这里也是根据next数组移动子串指针并且需要注意抽象出子串的概念。

所以在第六步中匹配成功以后主串子串移动，在这之后已经跳出循环了。而实际上next[4]在目标串中匹配是用不到的。

嗯。。要记住是先尝试匹配，成功后在向后移动指针，不匹配则重置指针。

这里的k=-1可以理解为当首位不匹配时移动指针的一个条件。

紧接着可以思考模式串"abcab"，"abcabd"，"ababab"等next数组的生成过程。理解kmp的重点在于next数组是如何生成的。

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/22853.html

结合kmp算法的匹配动画浅析其基本思想

摘要：写在最前本次分享一下通过实现算法的动画效果来试图展示的基本思路。算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。本次主要通过动画演示的方式展现朴素算法与算法对比过程的异同从而试图理解的基本思路。写在最前本次分享一下通过实现kmp算法的动画效果来试图展示kmp的基本思路。欢迎关注我的博客，不定期更新中—— 前置概念字符串匹配字符串匹配是计算...

wpw 2019-08-22 14:51 评论0 收藏0
字符串匹配算法之KMP模式

摘要：字符串的普通模式匹配普通模式匹配的原理不进行说明了，简单来说就是两个字符串的每个字符依次进行匹配。这篇文章主要是介绍KMP模式匹配算法，在正式介绍KMP之前我们先看一下普通模式匹配，由普通模式匹配在进一步的推导KMP模式会更容易理解。字符串的普通模式匹配普通模式匹配的原理不进行说明了，简单来说就是两个字符串的每个字符依次进行匹配。 public int match(String ...

NeverSayNever 2019-08-16 14:03 评论0 收藏0
KMP模式匹配算法（一）从暴力匹配切入

摘要：朴素的模式匹配算法这种算法又被称为暴力匹配算法。如果匹配失败，则回溯到主串的下一个位置重新逐位匹配。当然，在匹配算法中不同的输入会有不同的复杂度，最好的情况就是一开始就匹配成功。切入结束，下篇详解匹配算法最近在看关于算法方面的，正好看到关于KMP算法相关的部分，这里就做一个总结。假设我们有这样的一个主串 S = googlgomglegoogle 和一个子串 C = google 我...

xfee 2019-08-22 10:37 评论0 收藏0