现代网络搜索引擎一般使用基于字符串匹配的搜索方式，使用的软件核心之一是字符串模式匹配算法。网络特别是Internet的信息量极大，在相同的信息采集方式下网络搜索的时间主要取决于所使用的串匹配算法的效率。改善串匹配算法的特性或者时间复杂度，将有效提高网络搜索引擎的性能。所以算法的提出和后续改进的算法称为研究的重点。模式匹配主要有BF算法，KMP算法，BM算法及其改进算法，尤其是BM算法，在实际应用中非常著名，在此我们将对这几种算法做简单分析，分析前，我们做如下假定：
文本：text[0..n?1] n为文本长度 模式：pat[0..m?1]m为模式长度
2.1 BF算法
BF（Brute Force）算法又称为蛮力匹配算法[2]，这是一种效率很低的算法，其算法主要思想是模式的第一个字符与文本的第一个字符进行比较，如果相同，就继续比较后面的字符，否则，文本的起始位置加1，即模式右移一个位置，再进行比较，如果模式与文本中一段连续字符串都相同，则匹配成功，返回当时文本的起始比较位置，否则匹配不成功，实现过程：在串text和串pat中比较的起始下标i和j；循环直到text中所剩字符小于pat的长度或pat的所有字符均比较完（如果text[i]=pat[j]，则继续比较text和pat的下一个字符；否则将i和j回溯，准备下趟比较）；如果pat中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。
BF算法如下： Algorithm BF k=0;j=0;
while ((j<=m)&&(k<=n-m))
{ if (pat[j]==text[k]) { k++; j++;
} Else {
k=k-j+1;j=0; }
}
if (j= =m) Match found at text[k-m] else No match found
例子 1：
文本： astringsearchingexamplelienvolingrelatively 模式串：relative
1. astringsearchingexamplelienvolingrelatively relative
2. astringsearchingexamplelienvolingrelatively relative
3. astringsearchingexamplelienvolingrelatively relative
4. astringsearchingexamplelienvolingrelatively relative ：
32. astringsearchingexamplelienvolingrelatively relative
该算法简单，但是效率较低。时间复杂度：设匹配成功发生在text[i]处，则在i-1趟不成功的匹配中比较了（i-1）m次，第i趟成功匹配共比较了m次，所以总共比较了im次，因此平均比较次数是：m*(n-m+1)/2。最坏情况下要进行 m*(n-m+1)次比较，时间复杂度为O(m*n)。
2.2 KMP算法
由Knuth 等人提出的Knuth-Morris-Praa(KMP)算法[2]是对BF算法的很大改进，每次匹配失败时利用已经得到的“部分匹配”结果，将模式串向右移动若干位置后继续比较。
KMP算法的基本思想：将文本text和模式pat左端对齐进行比较，匹配text[i]和pat[j]时:若text[i]=pat[j]，则继续往前匹配比较;若text[i]?pat[j]，则文本中i不变，模式中j指向next[j]所指示位置。这可以提高匹配算法的效率，但相对比较复杂。KMP算法与BF算法在形式上极为相似。不同之处在于：当匹配过程中产生“失配”时，指针i不变，指针j退回到next[j]所指示的位置上重新进行比较，并且当指针j退至零时，指针i和指针j需同时增1。即若主串的第i个字符和模式的第一个字符不等，应从主串的第i+1个字符起重新进行匹配。实现过
程：在串text和串pat中比较的起始下标i和j；循环直到text中所剩字符小于pat的长度或T的所有字符均比较完（如果text[i]=pat[j]，则继续比较text和pat的下一个字符；否则将j向右滑动到next[j]位置，即j=next[j];如果j=0，则将i和j分别+1，准备下趟比较）；如果pat中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。
具体算法如下： Algorithm KMP
int KMP(char text[ ],char pat[ ],int next[ ] ) {
int i=0,j=0;
n=len(text);m=len(pat); while(i if (j= =-1||pat[j]==text[i]) {i++;j++;} else j=next[j] if(j>=m)return i-m; else return 0; } 数组next[j]表示当模式中第j个字符与正文中相应字符匹配失败时，在模式中需要一个新的和正文中该字符进行比较的字符的位置，这一位置只与模式本身有关，而与正文无关。求解模式的next函数的算法如下： get_next(char pat[ ],int next [ ],int m) { int j,k; j=0;k=-1; next[0]=-1; while (j if (k==-1||pat[j]==pat[k]) { j++; k++; next[j]=k; } else k=next[k]; } } 根据以上算法，以pat[ ]=‘abcac’和text[ ]=‘ababcabcacbab’为例，开始时，把模式串和正文左边对齐。 算法从左至右进行匹配，第一次匹配结束时，i=3，j=next[j]=3。将模式串向右移动，使得text[i]和pat[j]对齐。继续比较，如图2.1所示。 第一趟匹配：aabbi=3bacj=3i第二趟匹配：abaabbj=1第三趟匹配：ababcaabbccaabcj=5iccj=2aacci=11bai=7cacbabcabcacbabb 图2.1 KMP算法匹配过程 依上述的方法继续进行比较，直到匹配成功或与正文比较结束为止。时间复杂度：Ο(nm)，当m< 2.3 BM算法 1977年Boyer和Moore提出了全新的算法——Boyer-Moore(简称BM)算法[1]，它从另外一个角度出发提出一种比较新颖的方法来求解模式匹配问题。BM算法和KMP算法的差别是对模式串的扫描方式由自左至右变成自右至左，另一个差别是考虑正文中可能出现的字符在模式中的位置。这样做的好处是当正文中出现模式串中没有的字符时，就可以将模式串大幅度划过正文。匹配过程中模式从左向右移动，但字符的比较却从右向左，即按p[m-1]，p[m-2]，…p[0]的次序进行比较，在发现不匹配时，算法根据预先计算好的两个数组，将模式串向右移动尽可能远的距离，这两个数组称为shift和skip。 “坏字符”思想：定义skip数组，如果字符ch没有在pattern中出现，skip[ch]=m；如果字符ch在pattern中出现过，记e表示ch在pattern中出现的最后位置（下标从0开始），则skip[ch]=m-e-1。从右向左地把模式串同文本作比较，设匹配进行到比较text[k-m+1…k]和pattern[0…m-1]，从右至左一次检查text[k]，text[k+1]… text[k-m+1]当匹配失败发生在text[i]!=pattern[j](i在k-m+1到k之间，j在0到m-1之间)时，采用skip[text[i]]表示扫描文本的指针向前移动的位数。“坏字符”思想实际上是将text[i]在pattern中最后一次出现的位置与文本中的text[i]对齐后开始新的一轮匹配。 “好尾缀”思想：若pattern后部与text一致的部分之中，有一部分在pattern中其它地方出现，则可以将pattern向右移动，直接使这部分对齐，且要求这一部分尽可能的大。其基本算法和KMP中的next函数比较相似。 BM 算法的基本思想:模式串P和给定的文本T左端对齐，在扫描的过程中采用自右向左的扫描方式，一旦出现不匹配现象（失配），就可以使模式串P向右滑动一段距离，在滑动过程中采用了坏字符方法和好后缀方法，滑动的距离是两者之中的最大值。现对BM 算法详细描述如下：模式串P和给定的文本T左端对齐，自右向左开始扫描对比，如果匹配则继续向左扫描如果能够到达最左端，则说明匹配成功，如果扫描过程中遇到不匹配字符，则根据坏字符函数和好后缀函数中滑动距离较大的来使模式串右移，然后重复上面的操作。 坏字符函数的功能是：如果模式串P中某个字符P[i]和文本串中某个字符T[j]失配，而且T[j]不出现在模式串P中，那么模式串P右移至T[j]右边第一位，即P[1]等于T[i+1]；若在两者失配的同时，T[j]在P中出现（可能不止一次），则将T[j]和P中最右边的相等的字符对齐。 好后缀函数的功能是:如果模式串P中后面的k位已经和T中有一部分匹配成功（标记匹配成功的部分为P1子串），此时检查模式串P中前边m-k位是否存在P1子串，若存在，则将模式串P右移使之对齐。如果不存在P1子串，则检查在模式串P中前边m-k位是否存在P1子串的任意子串，如果存在，则右移模式串使其对齐。如果两者皆不存在，此时可直接将模式串向右移动m，BM算法在匹配失败的时候将模式串向右移动，通过坏字符函数和好后缀函数来确定移动的长度，具有了较高的匹配速率。但是其算法在好后缀函数的处理上面非常难以理解和实现，而且需要将好后缀函数和坏字符函数获得的模式串移动的值进行比较，取其最大值，因此匹配速率也是可以再提高的。 假定失配发生时的情况如图2.2所示，此时已经匹配的部分为u，正文的b字符与模式的a字符发生失配。