C和C++文本搜索中的精确匹配算法下
更新时间:2017-05-31 作者:丁老师 阅读:1443
在MP算法之后,再一次衍生了KMP算法。KMP算法与MP算法可谓是一脉相承。
3,KMP算法核心思想是试图充分利用先前匹配过程中已经得到的结果来避免频繁回溯。也因此MP算法和KMP算法及其相似,很容易让人将MP算法和KMP算法混淆。
KMP算法的失效匹配函数C语言实现方式如下:
voidpreKMP(const char * dest, int m, intkmpnext[])
{
inti , j;
i=0;
j=kmpnext[0]=-1;
while(i<m)
{
while(j>-1 &&dest[i]!=dest[j])
j=kmpnext[j];
i++;
j++;
if(dest[i]==dest[j])
kmpnext[i]=kmpnext[j];
else
kmpnext[i]=j;
}
}
4,BM算法是以上搜索算法的逆向思维,在使用BM算法时,目标字符串由左向右移动,而字符的比较却是由右向左进行。当文中字符与目标字符不匹配时,则根据预先定义好的“坏字符偏移函数”和“好后缀偏移函数”计算出偏移量。
BM算法的执行过程相当复杂,但由于该算法具有很高的执行效率,在实际中应用广泛。
5,BMH算法是在BM算法上的改进算法,因在应用中,坏字符偏移函数的应用次数远远大于好后缀偏移函数次数,坏字符偏移函数在匹配过程中起着移动指针的主导作用,因此,在使用中,只是用坏字符偏移函数也非常有效。BMH是对BM算法的改进,也是一种简化,执行非常简便,而且效率也较为可观。
文本的精确匹配算法在以上的各种算法中各有优劣,据实际需要,可选择合适的算法达到最好的效果。
就业学员
-
姓名:郭凡凡
院校:阜阳师范学院
就职:佳戴
职位:软件工程师
月薪:10000
-
姓名:陈祥龙
院校:中北大学
就职:美囤妈妈
职位:软件工程师
月薪:9000
-
姓名:陈建伟
院校:南昌航空大学
就职:SONY
职位:嵌入式工程师
月薪:8000