4.3.1　Brute－Force算法

1.算法基本思想

Brute－Force算法也称为朴素的模式匹配算法，其基本思想是：从主串S＝“s0s1…sn－1”的第一个字符起，与模式串T＝“t0t1…tm－1”的第一个字符比较。若相等，则依次比较后续字符；否则，从主串的第二个字符起，重新与模式串中的字符比较。重复这个过程，直至模式串中的每个字符依次与主串中的一个连续字符序列相等，则匹配成功；否则，匹配失败。下面我们以一个例子来演示该算法匹配的过程。

例4.2 设主串S＝“cddcdc”，模式串T＝“cdc”，请在主串S中寻找模式串T。

S的长度为n＝6，T的长度为m＝3，用变量i指示主串S当前比较字符的下标，用变量j指示模式串T当前比较字符的下标。Brute－Force算法模式匹配的具体过程如图4－3所示。

从上述匹配过程我们可以推知两点：

（1）若在前k－1次比较中未匹配成功，则第k次比较是从S中的第k个字符Sk－1开始和T中的第一个字符T0比较。

（2）设某一次匹配有Si≠Tj，其中0≤i＜n，0≤j＜m，i≥j，则应有Si－1＝Tj－1，…，Si－j＋1＝T1，Si－j＝T0。再由（1）可知，下一次比较主串的字符Si－j＋1和模式串的第一个字符T0。

通过上面的介绍，我们可以看到整个算法非常简单，但期间存在着大量的回溯现象。如第一次匹配失败后，指针i由2回溯到1，以便进行第二次匹配。下面我们给出算法的C语言实现。

图4－3 Brute－Force算法模式匹配过程

2.算法实现

算法4.1 Brute－Force算法

3.算法时间复杂度分析

Brute－Force算法简单，易于理解，但某些时候时间效率不高。主要原因就是前面我们提到的指针回溯问题。在主串和子串已有相当多个字符经比较相等的情况下，只要有一个字符比较不相等，便需要把主串的比较位置（即算法中变量i的值）回退。设主串的长度为n，子串的长度为m，则Brute－Force算法在最好情况下的时间复杂度为O（m），即主串的前m个字符刚好等于模式串的m个字符。

该算法在最坏情况下的时间复杂度为O（n×m）。其分析如下：当模式串的前m－1个字符序列和主串的相应字符序列比较总是相等，当模式串的第m个字符和主串的相应字符比较总是不等时，模式串的m个字符序列必须和主串的相应字符序列块共比较n－m＋1次，每次比较m个字符，总共约需要比较m（n－m＋1）次，因此其时间复杂度为O（n×m）。