C和C++文本搜索中的精确匹配算法上

在文本内容中，都是以字符串的方式来表示，此时要精确搜索文本中是否存在目标文本，也即是搜索在大字符串中搜索目标字符串。这种精确匹配在计算机系统中有着较为广泛的应用，如文本编辑，拼写检查，情报搜索，互联网搜索等。

较为常见的字符串精确匹配算法有以下几种：

1，BF算法

BF即英文Brute Force 算法是算法模式匹配中最简单，最直观的算法。该算法的基本思想是从主字符串T(t0,t1,t2,t3,….tn-1)中的第m个字符起和目标第1个字符比较，如果相等，则继续逐个比较后续字符；比较过程中一旦发现不相等，则回溯到源字符串的m+1个字符，重新匹配，依次类推，知道目标字符串每个字符和源字符串的一个连续的字符序列相等，就匹配成功，否则匹配失败。

2，MP算法

MP算法是对BF算法的极大改进，利用了已经得到的并且存贮的比较结果，在后续比较过程中直接调用这些比较结果，大大的提高了算法的效率。在MP算法中，，最为关键的是寻找匹配失效函数，而一旦目标字符串给定，不管源字符串的取值如何，失效函数均为同一个，也即是失效函数与源字符串无关。

下面给出目标字符串的失效函数C语言代码实现方法：

voidpreMP(const char *dest, intm,intmpnext[])

{

inti, j;

i=0;

j=mpnext[0]=-1;

while(i<m)

{

while(j>-1 && x!=x[j])

j=mpnext[j];

mpnext[++i]=++j;

}

}

其中函数的参数说明如下：

dest：目标字符串

m:目标字符串的长度

mpnext:用来存贮失效发生时下一轮比较的目标字符串的起始比较位置。