模式匹配：从BF算法到KMP算法

模式匹配：从BF算法到KMP算法2015-09-24模式匹配

子串的定位操作通常称为串的模式匹配。模式匹配的应用很常见，比如在文字处理软件中经常用到的查找功能。我们用如下函数来表示对字串位置的定位：

int index（const string &Tag,const string &Ptn,int pos）

其中，Tag为主串，Ptn为子串（模式串），如果在主串Tag的第pos个位置后存在与子串Ptn相同的子串，返回它在主串Tag中第pos个字符后第一次出现的位置，否则返回-1。

BF算法

我们先来看BF算法（Brute-Force，最基本的字符串匹配算法），BF算法的实现思想很简单：我们可以定义两个索引值i和j，分别指示主串Tag和子串Ptn当前正待比较的字符位置，从主串Tag的第pos个字符起和子串Ptn的第一个字符比较，若相等，则继续逐个比较后续字符，否则从主串Tag的下一个字符起再重新和子串Ptn的字符进行比较，重复执行，直到子串Ptn中的每个字符依次和主串Tag中的一个连续字符串相等，则匹配成功，函数返回该连续字符串的第一个字符在主串Tag中的位置，否则匹配不成功，函数返回-1。

用C++代码实现如下：

/* 返回子串Ptn在主串Tag的第pos个字符后（含第pos个位置）第一次出现的位置，若不存在，则返回-1 采用BF算法，这里的位置全部以从0开始计算为准，其中T非空，0<=pos<=Tlen */int index（const string &Tag,const string &Ptn,int pos）{int i = pos;//主串当前正待比较的位置，初始为posint j = 0; //子串当前正待比较的位置，初始为0int Tlen = Tag.size（）;//主串长度int Plen = Ptn.size（）;//子串长度 while（i<Tlen && j<Plen）{if（Tag[i] == Ptn[j]） //如果当前字符相同，则继续向下比较{ i++;j++;}else //如果当前字符不同，则i和j回退，重新进行匹配{ //用now_pos表示每次重新进行匹配时开始比较的位置，则//i=now_pos+后移量，j=0+后移量//则i-j+1=now_pos+1,即为Tag中下一轮开始比较的位置i = i-j+1;//Ptn退回到子串开始处j = 0;}} if（j >= Plen）return i - Plen;elsereturn -1;}

调用上面的函数，采用如下代码测试：

int main（）{char ch;do{string Tag,Ptn;int pos;cout<<"输入主串：";cin>>Tag;cout<<"输入子串：";cin>>Ptn;cout<<"输入主串中开始进行匹配的位置（首字符位置为0）：";cin>>pos; int result = kmp_index（Tag,Ptn,pos）;if（result ！= -1）cout<<"主串与子串在主串的第"<<result<<"个字符（首字符的位置为0）处首次匹配"<<endl;elsecout<<"无匹配子串"<<endl; cout<<"是否继续测试（输入y或Y继续，任意其他键结束）：";cin>>ch;}while（ch == "y" || ch == "Y"）;return 0;}

测试结果如下：