公开(公告)号：CN103500178A

公开(公告)日：2014-01-08

申请号：CN201310406833.3

申请日：2013-09-09

Applicant: 中国科学院计算机网络信息中心

Inventor： 胡新静 ,  许家铭 ,  李晓东 ,  金键

IPC: G06F17/30

Abstract: 本发明公开了一种FS算法最差情况下的快速多模式匹配方法。本方法为：1）将模式串集合转换成反向有限自动机，计算坏字符转移函数skip1和好后缀转移函数skip2；2）构建自动机中状态s在遇到字符c时发生失配所用词典，包括：匹配串u在其他模式串中的所有深度大于u的出现位置，后缀suffix(u)在其他模式串中的所有深度大于suffix(u)的出现位置；3）设置一倒计时值cdown；将待匹配文件与模式串集合进行匹配，当skip2跳转时，记录当前失配状态对应的词典，跳转后每匹配一个字符cdown减1；若发生skip1跳转，则cdown增加skip1的跳转值；4）当cdown为0且记录的词典不为空时，利用当前记录的词典搜索对应的子串终止状态，找到相应的跳转位置，继续匹配。

公开(公告)号：CN103500178B

公开(公告)日：2017-01-11

申请号：CN201310406833.3

申请日：2013-09-09

Applicant: 中国科学院计算机网络信息中心

Inventor： 胡新静 ,  许家铭 ,  李晓东 ,  金键

IPC: G06F17/30

Abstract: 本发明公开了一种FS算法最差情况下的快速多模式匹配方法。本方法为：1）将模式串集合转换成反向有限自动机，计算坏字符转移函数skip1和好后缀转移函数skip2；2）构建自动机中状态s在遇到字符c时发生失配所用词典，包括：匹配串u在其他模式串中的所有深度大于u的出现位置，后缀suffix(u)在其他模式串中的所有深度大于suffix(u)的出现位置；3）设置一倒计时值cdown；将待匹配文件与模式串集合进行匹配，当skip2跳转时，记录当前失配状态对应的词典，跳转后每匹配一个字符cdown减1；若发生skip1跳转，则cdown增加skip1的跳转值；4）当cdown为0且记录的词典不为空时，利用当前记录的词典搜索对应的子串终止状态，找到相应的跳转位置，继续匹配。