您当前位置:设计在线网 >> 自动控制理论 >> 浏览文章

单模式匹配算法--简单的单模式匹配算法

分享到:
本文章讲述了单模式匹配算法--简单的单模式匹配算法.

[算

法]单模式匹配算法

 

一个高效简单的单模式匹配算法。简单讲就是"滑动窗口"模式,利用自定义HashCode相加,只扫描一次字符数组,匹配出所有。

有A,C,G和T,分别代表组成DNA的四种核苷酸-腺嘌呤,胞嘧啶,鸟嘌呤,胸腺嘧啶。典型的他们无间隔的排列在一起,例如序列AAAGTCTGAC,我们从中要查找GT,则可先自定义出GT的HashCode为:103+116=219,然后每次跟序列AAAGTCTGAC的两位字符HasdCode快速比较,每次m-1个Hash重用。若相等则逐字符严格核实。

可以把"GT"隐喻为一个滑动的"小窗口"。每滑动一位,比较一次!附代码:

publicboolBadwordParser(stringtext,stringbad){inttextLen=text.Length;intoffset=bad.Length;if(textLenoffset)returnfalse;longbadHashcode=0;longprefWindowHashcode=0;forinti=0;ioffset;i++){badHashcode+=char)bad[i];prefWindowHashcode+=char)text[i];}intl=0;intinnerloop=(textLen-offset)+1;do{if(badHashcode==prefWindowHashcode){unsafe{fixedchar*pChar=bad.ToCharArray(0x00,offset)){forintk=0;koffset;k++if(text[l+k]!=pChar[k])break;}returntrue;}}if(textLen(offset+l))prefWindowHashcode-=char)text[l]-char)text[l+offset];}while++innerloop));returnfalse;}跟string.IndexOf性能比较:前提:大小为364K的《明朝那些事》的Test.txt,从中随机搜索一个词语,比如"魏忠贤"(注:此词在文中位置不定),循环查找10000次

结果如下:

若匹配内容不存则成线性同比增长。

推荐阅读:
使用.NET非对称加密算法实例介绍
电气工程及其自动化专业毕业设计参考题目
如何给重要文件加密的方法介绍
推荐文章  
赞助商链接  
热门排行  
主题推广  
中国设计在线网 All Rights Reserved. 互联网违法和不良信息举报
信息产业部备案号:湘ICP备09001063号