1、BDM算法使用后缀自动机搜索子串。后缀自动机决定字符串U是否为模式串P的子串图示如下:
1)可以在O(|U|)时间内确定个字符串U是否为字符P的子串,U是P的子串,当且仅当P的后缀自动机中存在一条要从初始状态开始的标号为U的路径,注意该路径不一定要到达终止状态。从上图可看出,CB也是CBA的子串。
2)可以识别模式串的所有后缀。从初始状态到某个终止状态的路径上字符组成的字符串是模式串P的一个后缀。
3)模式串P的对应的后缀自动机可以O(m)完成。
2、在文本T=T1 T2 T3。。。。。Tn中搜索模式串P=P1 P2。。。Pm
1)首先构建起模式串P的反转P(rv)=Pm P(m-1)....P1对应的后缀自动机,反转的目的是为了得出P的前缀自动机。
2)算法使用后缀自动机在搜索窗口中从后向前搜索模式串的子串。搜索过程如果到达了终止状态,并且对应的不是整个模式中,则它在窗口中的位置存在变量last中,此时,可以说找到了当前识别的P的最长前缀,因为是P的反转的最长后缀。该缀从last开始到窗口尾处结束
3、搜索过程以下2种可能的方式结束:
1)在识别一个子串时失败了,即读入一个字符σ,在P的反缀自动机的当前状态没有σ转移,这时将窗口向右移动,使得它的起始位置与last对齐
2)抵达了窗口的起始位置,意味着整个模式串P被成功匹配,报告一个成功匹配,并像1)一样移动窗口。
- 大小: 27.1 KB
分享到:
相关推荐
HF-BDM-S0812用户手册 欢迎下载
产品型号:1321XNSK-BDM支持器件:MC1321X描述:Freescale第二代ZigBee开发平台, 网络开发套件,可以用于演示和开发更复杂的网络,包括2个 1321x-SRB (Sensor Reference Board) boards, 一个1321x-NCB (Network ...
产品型号:13192DSK-BDM-A00支持器件:MC13192描述:低成本开发套件,应用于IEEE 802.15.4 无线网络的开发,本套件包括所有需要用到的软件,硬件,和文档价格/1片(套):¥3,200.00
产品型号:1321XDSK-BDM支持器件:MC1321X描述:包括硬件板,线缆,电池,电源适配器,应用实例, USB Multilink BDM 编程器/调试器.支持SMAC 及IEEE 802.15.4 PHY/MAC, 软件含CodeWarrior Development Studio for HCS08 ...
BDM-01- Microsoft Vision and Strategy
这个是飞思卡尔XS128等系列单片机BDM下载器仿真器,资料里是个人制作BDM的全过程,包括原理图、PCB、固件,PCB可以直接打板,已经经过批量试制
BDM 源程序 BDM drive program
HCS08的BDM仿真器资料,包括原理图、源码
飞思卡尔 智能车 usbdm制作方法 及相关程序 含PCB文件 usbdm制作方法
飞思卡尔单片机BDM驱动程序,MC9S12G128单片机。
各种版本的BDM驱动,里面有支持win7 64位的
本 BDM 是根据飞思卡尔官方论坛TBDML 制作资料为基础,参考清华大学 S12BDM 实物而设计制作的开源BDM 工具。价格低廉、制作方便、方案成熟, 是飞思卡尔S12 系列16 位单片机性价比最高的开发工具。 原先本产品在淘宝...
freescale xs128BDM下载方式,BDM驱动破解版下载
Informatica BDM培训教程v1.0 - Copy.docx
自己编制的怎么使用BDM 直接烧写程序
2009最新款三合一HCS08 HCS12 Coldfire v1 BDM调试器,来自Freescale应用开发研究中心
飞思卡尔智能车调试用BDM的编程器,有助于个人制作BDM的智能车爱好者 更好的的学习
学习单片机,需要安装驱动,bdm就是安装所需要的驱动
code warrior BDM WIN7 64位驱动,寻找不易,且行且珍惜
龙丘BDM手动下载程序的步骤 龙丘BDM手动下载程序的步骤