 多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页 首页 上一页 下一页 尾页 | |
算法讲堂 |
|
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。 本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。 现本栏目的内容处于不断添加中，请随时关注。 |
|
| 算法讲堂－》朴素字符串匹配【讲解】 |
|
算法介绍：
朴素字符串匹配算法是一个简单的字符串匹配算法，其原理可以简单描述为以下： 假设有两个字符串s和a，其中s是被匹配的字符串，a是要匹配的子字符串，其匹配过程为： （1）从s的第一个字符开始与a匹配：取s的第一个字符与a的第一个字符比较，如果相同的话，取s的下一个字符与a的下一个字符比较，如此，直到比较到a的最后一个字符，如果此间所有比较都相同的话，那么说明在s中存在子字符串a。 （2）如果在上述比较过程中，有一次比较不相同的话，那么就从s的第二个字符开始与a匹配：取s的第二个字符与a的第一个字符比较，如果相同的话，取s的下一个字符与a的下一个字符比较，如此，直到比较到a的最后一个字符，如果此间所有比较都相同的话，那么说明在s中存在子字符串a。 （3）按照以上方式，一直比较到字符串s的结尾，匹配算法结束。 时间复杂度分析： 设s的长度为n，a的长度为m， （1） 当n >= m 最坏的情况是，n-m+1次的比较都是比较到a的最后一个字符，即每次比较次数为m次；剩余m-1次比较，比较次数是一个从m-1开始的增量为-1的等差数列,共有m-1项。根据以上计算出该算法的比较次数为： (n-m+1)m+（(m-1)+1）*(m-1)/2 = (n-1/2)m – m2 /2 = (2n-1-m2)/2， 即该算法的最大时间复杂度为：O（（（2n-1-m2）/2））。 （2） 当n < m 最坏的情况是，比较次数是一个从n开始的增量为-1的等差数列，共有n项。这样计算出的算法比较次数为（（n+1）*n）/2，所以其时间复杂度为O（n2）。 学习建议及任务： 以上算法分析，完全是一个没有进行任何优化的原始算法原理，我们应该可以看到，当s的长度小于a的长度的时候，是绝对不可能匹配成功的。所以，此时的匹配运算完全是没有必要的。要求学习者自己动手，重新编写该匹配算法，并完成n<m时的算法优化，使算法达到O（(n-m+1)m）的时间复杂度，并利用该算法实现一个查找给定关键字的小程序。 [07/10/12] |