基于snort的入侵检测系统的研究(16)

式串P分成两部分，一部分是首字符串，记作head_string，一部分是尾字符串首，记作foot_string。其中首字符串设为模式串P中的一个最长的真首子串(len(head_string)<len(P))，把它作为新的模式串和正文T匹配，当发生不匹配时，利用Sunday算法移动尽可能远的距离；当匹配时，再用尾字符串foot_string与文本串T相应位置的字符进行匹配，当foot_string匹配失败时，移动head_string到foot_string刚刚匹配失败的位置，继续匹配。当foot_string也匹配成功时，则整个匹配过程完成，匹配成功。

4.2.1 确定首字符串

设模式串为P[1 M]，文本串为T[1 N]，首字符串为head_string。为了要找最长的子串，在初始匹配时，令head_string=P[1 M]作为新的模式串，若不符合最长字串的要求，则再继续尝试head_string=P[1 M-1]， 依此类推。获取head_string串的方法是：设模式串head_string的最右边的元素为head_string[j]，文本串T的T[i]是紧跟在head_string[j]和正文对齐的元素之后的元素。如图4-3所示：

文本T

head_string

图4-3 head_string获取过程

然后用 T [i]依次去匹配head_string[l j-1]， 一旦发现匹配，则将head_string的最后一个元素去掉，生成新的head_string，进入下一轮匹配（T [i-1]依次去匹配head_string[l j-2]）；

如果head_string和T[i]不匹配，则有两种处理方式：

(1)如果T[i]=head_string[j]时，则将串head_string右移j+l个单位；

(2)如果T[i]≠head_string[j]时，则将串head_string右移j+2个位。

如果按照这个规则head_string串一直能移动到正文T的最右端，则成功找到head_string；否则将head_string 的最后一个元素去掉，生成新的head_string，