特征码扫描技术是反病毒技术中的常规武器，虽然特征码扫描技术有着一定的局限性，但是，改进的基于特征码扫描技术的广 谱特征串过滤技术却有着无比的优越性和广阔的应用前景。但是，无论是上面提到的哪种技术，最终都难以逃脱扫描算法的效率要求。而学过《数据结构》的读者应 该知道一种快速的字符串扫描算法叫做“模式匹配算法”，这种算法可以对字符串进行快速扫描。但是，深入进去就会发现，我们的特征码扫描算法中经常会用到通 配符，如：%和*（这里我令%匹配一个字符，*匹配32个字符），对于这样一些非常规的串，没有现成的算法可以引用。笔者在做防治木马技术的研究中，对常 规的模式匹配算法进行了改进，写出了如下的快速查找算法，暂且命名为“半回溯的模式匹配算法”，以与常规的“无回溯的模式匹配算法”区别。
这里，我之所以称之为“半回溯”，就是因为在对通配符进行匹配时要进行适当的回溯，以减少因为采用通配符所带来的过长推进，虽然这是一种带有回溯的算法， 但是实际上它的效率并不比“无回溯的模式匹配算法”低多少，其对算法的效率不能构成真正的威胁。这个算法比较抽象，如果没有基础的读者最好先回头看一下 《数据结构》的教材中的“无回溯的模式匹配算法”，会对您接下来对算法的理解产生很大的帮助。光说不练，不是好汉，下面我们就开始艰辛而又刺激的模式匹配 算法之旅。
对于“无回溯的模式匹配算法”，我不想做过多的说明，因为相关书籍上已经说得够明白了。下面，我们一起来看一下带通配符的半回溯的匹配算法（用%号匹配一个字符，用*匹配32个字符）：
1.[初始化]
i=1; j=1;
counter1=0; counter2=0;
2.[利用next[i]反复进行比较，直到i等于m+1]
循环 当i<=m且j<=n时，反复执行
若（p[i]!=’*’且p[i]==t[j]）
则i=i+1; j=j+1;
否则若p[i]==’%’
则 i=i+1; j=j+1; counter1=counter1+1;
否则若p[i]==’*’
则i=i+1; j=j+32; counter2=counter2+1;
否则若next[i]>0
则i=next[i] j=j – (counter1+counter2*32);counter1=0;counter2=0;
否则
i=1; j=j – (counter1+counter2*32);j++;counter1=0;counter2=0;
其中，counter1是用来统计%的个数，而counter2用来统计*的个数，其中m是子串的长度，n是被搜索串的长度。每次碰到子串中有%的时候就 自动将counter1加一，若是碰到counter2就自动将counter2加一。i用来指明子串的当前的比较的位置，而j用来指明被搜索串当前比较 的位置，如果一旦子串与被搜索串不能满足搜索条件，就要将被搜索串的比较位置进行回溯，以回到被通配符漏过的字符的个数，以便重新匹配。
这里，涉及到了与“无回溯的模式匹配算法”中相同的要使用的Next数组，其中，Next数组的计算方法如下：
1.[初始化]
j=0; i=1;
next[1]=0;
2.[反复比较计算next[i+1]
循环 当i<m时，反复执行
(1)[找出p1p2…pi中最大的相同的前缀和后缀，并将长度送j]
循环 当j>0且p[i]!=p[j] 且p[i]!=’%’且p[j]!=’%’时，反复执行
j=next[j]
(2)[计数器加1]
i=i+1; j=j+1;
(3)[计算next[i]]
若p[i]==p[j]或p[i]==’%’或p[j]==’%’
则next[i]=next[j];
否则next[i]=j;
Next数组的计算方法，与“无回溯匹配算法”稍有不同，因为%用来匹配一个字符，所以对于%的处理，可以看作比较的字符相等的情况来处理，而对*的比较，无论如何一个字符都不可能与一个32字符的字符串相等，所以对于*始终认为不相等。
这个算法的描述，无论我作何解释，读者总会感觉到有一些抽象，而难于真正理解。下面，笔者写了一个简单的程序，来对这个算法进行测试，希望对您会有所帮 助。这个程序是在VC6.0的控制台下运行的，非常简单，基本上就上将以上的算法翻译成了C++语言。源程序可以在附书光盘中找到，名称为“带通配符的无 回溯模式匹配算法源程序”。
在这个程序中，首先就是要建立一个子串和被搜索串，并确定算法中提到的m和n的值，如下所示。
//被搜索的串
char* t="nihaoaxishanchangshanchangaoyejiehhe*%dfisd%shanchashanchanghongioejw";
//子串
char* p="shanchang%*%hong";
//next数组中元素的个数等于子串的长度
int next[16];
int i,j;
//initialize variable
j=0;i=1;next[0]=0;
接下来，要计算next数组的值，对上面的算法进行翻译，得到如下代码。
//计算next数组的循环
while(i<16)
{
while(j>0&&p[i-1]!=p[j-1]&&p[i-1]!=’%’&&p[j-1]!=’%’)
j=next[j-1];
i++;
j++;
if(p[i-1]==p[j-1]||p[i-1]==’%’||p[j-1]==’%’)
next[i-1]=next[j-1];
else
next[i-1]=j;
}
有了至关重要的next数组之后，就要使用改进了的模式匹配算法，从被搜索串中搜索出子串，代码如下：
//模式匹配的循环
i=1;
j=1;
int counter1=0,counter2=0;
while(i<=16&&j<=69)
{
if(p[i-1]!=’*’&&p[i-1]==t[j-1])
{i++;j++;}
else if(p[i-1]==’%’)
{
i++;
j++;
counter1++;
}
else if (p[i-1]==’*’)
{
i++;
j+=32;
counter2++;
}
else if (next[i-1]>0)
{
i=next[i-1];
j-=(counter1+counter2*32);
counter1=0;
counter2=0;
}
else
{
i=1;
j-=(counter1+counter2*32);
j++;
counter1=0;
counter2=0;
}
//如果I等于17，说明对子串的搜索已经走到尽头，并搜索到了子串，跳出循环。
if(i==17) break;
}
如果您需要使用这个算法进行特征码的查找，可以直接将其中的计算next数组和模式匹配的部分进行移植。
到这里，基本上将要说的都说完了，可能您对这个算法还是有一些迷惑，如果您对其的正确性有疑问的话，可以使用上面的程序，对不同的子串和被搜索串进行操 作。另外，如果您对next数组不太了解，还是建议您找出教材来好好看一下。本算法的效率是比较高的，至于它的计算复杂度，我想在这里我就不能做过多的说 明了，有兴趣的读者，或者从事反病毒研究的读者，希望能对你们有一定的帮助，同时，如果有不对的地方，可以在黑防的论坛上面提一下，以期获得改进。
后记：对于一个真正的程序员来说，其任务决不应该仅仅只是机械地拖拖控件，动动鼠标。更重要的应该是编程开始前的软件的整体安排和设计，而相关算法设计也 应该是非常重要的一部分。对于一个扫描软件来说，其扫描算法的设计也定是其精华所在。本文专门对算法进行相关分析，希望能够对您有所启发。