专利详情

专利名称	一种FS算法最差情况下的快速多模式匹配方法
申请号	CN201310406833.3	专利类型	发明专利
公开（公告）号	CN103500178A	公开（授权）日	2014.01.08
申请（专利权）人	中国科学院计算机网络信息中心	发明（设计）人	胡新静;许家铭;李晓东;金键
主分类号	G06F17/30(2006.01)I	IPC主分类号	G06F17/30(2006.01)I
专利有效期	一种FS算法最差情况下的快速多模式匹配方法至一种FS算法最差情况下的快速多模式匹配方法	法律状态	实质审查的生效
说明书摘要	本发明公开了一种FS算法最差情况下的快速多模式匹配方法。本方法为：1）将模式串集合转换成反向有限自动机，计算坏字符转移函数skip1和好后缀转移函数skip2；2）构建自动机中状态s在遇到字符c时发生失配所用词典，包括：匹配串u在其他模式串中的所有深度大于u的出现位置，后缀suffix(u)在其他模式串中的所有深度大于suffix(u)的出现位置；3）设置一倒计时值cdown；将待匹配文件与模式串集合进行匹配，当skip2跳转时，记录当前失配状态对应的词典，跳转后每匹配一个字符cdown减1；若发生skip1跳转，则cdown增加skip1的跳转值；4）当cdown为0且记录的词典不为空时，利用当前记录的词典搜索对应的子串终止状态，找到相应的跳转位置，继续匹配。