【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
昨天我们编写了简单的字符查找函数。虽然比较简单,但是也算能用。然而,经过我们仔细分析研究一下,这么一个简单的函数还是有改进的空间的。在什么地方改进呢?大家可以慢慢往下看。
下面的代码是优化前的代码,现在再贴一次,这样分析起来也方便些:
不知道朋友们发现没有,原来的while条件中有一个很费时的操作。那就是每次str移动的时候,都需要判断str的长度大小。如果str的长度远大于data的长度,那么计算str长度的时间是相当可观的。
上面的代码很好地解决了长度判断的问题,这样一来每次比较的长度很短,只要判断len的大小字符长度即可。但是,我们还不是很满足,如果两者不比较岂不更好。那么,有没有这个可能?我们发现,如果str在每次比较不成功的时候,就会自己递增一位。那么我们只要判断这一位是不是‘\0’不就可以了吗?所以说,我们的代码还可以写成下面的形式。
和上面第一次的优化不同,我们在进入while之前会判断两者的长度区别,但是经过第一次判断之后,我们就再也不用判断了,因为接下来我们只要判第n个元素是否为‘\0’即可,原来的n-1个元素我们已经判断过了,肯定是合法的元素。为什么呢?大家可以好好想想。
(二)、KMP算法
KMP算法本质上说是为了消除查找中的多余查找步骤。怎么就产生了多余的查找步骤了呢。我们可以用示例说话。假设有下面两个字符串:
A: baaaaabcd
B: aaaab
那么这两个查找的时候会发生什么现象呢?我们可以看一下:
我们发现B和A在从第2个元素开始比较的时候,发现最后一个元素是不同的,A的第6个元素是a,而B的第5个元素是b。按照普通字符串查找的算法,那么下面A会继续向右移动一位,但是事实上2-5的字符我们都已经比较过了,而且2-5这4个元素正好和B的前4个元素对应。这个时候B应该用最后一位元素和A的第7位元素比较即可。如果这个计算步骤能省下,查找的速度不就能提高了吗?
【预告: 下面一篇博客介绍KMP的编写和多核查找算法】
分享到:
相关推荐
字符串查找KMP算法
KMP 模式匹配算法实例 C++源码 字符串查找
kmp字符串查找算法 最近复习数据结构,在这备个份
字符串相似度算法 字符串相似度算法 字符串相似度算法 字符串相似度算法 相似度 字符串
用java查找汉字字符串有多重算法,其中Boyer-Moore是基本算法之一。算法简洁,开发容易,是进行搜索引擎开发的重要算法之一。
一本全面彻底讲解字符串查找算法的书。 书中讲解了34个字符串查找算法的思想。每个算法都有适用性的描述。每个算法都有逐步推演的例子(图解)。每个算法都有代码(C语言)。每个算法都有复杂度分析。每个算法都有...
比Boyer-Moore更快的字符串查找算法
基于Qt写了一个字符串加密的算法模块(有源码),并封装成了动态库,有测试用例。实现的加密解密算法是AES加密对称算法和BlowFish。用户可以直接用动态库,也可以用源码编译。
字符串的查找是数据库应用中必不可少的操作,而且每种数据库产品(ORACLE、DB2、SYBASE、MS SQL SERVER、MYSQL等等)也都提供了对应的字符串处理函数,比如...本文介绍了通用固定长度编码格式的字符串查找算法的实现。
a fast string searching algorithm原文
关于经典算法--压缩字符串(将字符串内连续重复出现的字符进行压缩),个人的想法
数据结构,BF算法,替换字符,查找字符,利用BF算法,一个一个回溯进行比较!~
运行程序之后输入任意的字符串,将字符串转化成二进制数字字符串,然后利用LZ78算法实现对二进制字符串压缩解压,最后再恢复原来的字符串
字符串匹配算法之Horspool算法(英文原版)
本程序是用C语言编写的实现链式字符串运算的算法。简单,里面的注释很详细,对初学者很实用
字符串匹配算法的演示程序,包括了平凡算法、KMP、RK、BM四种,有界面,统计展示移动和比较次数等信息。
字符串的模式匹配算法——KMP的C++实现。
字符串相似度比较算法,可比较不同长度的任意两个字符串的相似度,以百分比显示。
字符串加密,使用MD5或者SHA算法对字符串加密
Java 实现推荐系统 两个字符串 余弦相似度 算法。