模式匹配

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

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;  //主串当前正待比较的位置，初始为pos
	int j = 0;   //子串当前正待比较的位置，初始为0
	int Tlen = Tag.size();  //主串长度
	int Plen = Ptn.size();  //子串长度
	
	while(i
  
   = Plen)
		return i - Plen;
	else
		return -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<<主串与子串在主串的第<
  
   >ch;
	}while(ch == 'y' || ch == 'Y');
	return 0;
}
  

测试结果如下：

以上算法完全可以实现要求的功能 ，而且在字符重复概率不大的情况下，时间复杂度也不是很大，一般为O（Plen+Tlen）。但是一旦出现如下情况，时间复杂度便会很高，如：子串为“111111110”，而主串为 “111111111111111111111111110” ，由于子串的前8个字符全部为‘1’，而主串的的前面一大堆字符也都为1，这样每轮比较都在子串的最后一个字符处出现不等，因此每轮比较都是在子串的最后一个字符进行匹配前回溯，这种情况便是此算法比较时出现的最坏情况。因此该算法在最坏情况下的时间复杂度为O（Plen*Tlen），另外该算法的空间复杂度为O（1）。

KMP算法

KMP算法的主要思想

上述算法的时间复杂度之所以大，是由于索引指针的回溯引起的，针对以上不足，便有了KMP算法。KMP算法可以在O（Plen+Tlen）的时间数量级上完成串的模式匹配操作。其改进之处在于：每一趟比较重出现字符不等时，不需要回溯索引指针i，而是利用已经得到的部分匹配的结果将子串向右滑动尽可能远的距离，继续进行比较。它的时间复杂度为O（Plen+Tlen），空间复杂度为O（Plen），这从后面的代码中可以看出。

以下面两个字符串的匹配情况来分析

主串：ababcabcacbab

子串：abcac

如果采用简单的BF算法，则每趟比较i都要回退，而采用KMP算法，每趟比较时，i保持不变，只需将j向右滑动即可，也即是减少了中间一些趟次的比较。KMP算法匹配以上两个字符的过程如下（黄色部分表示匹配成功的位置，黄色部分的第一个字符表示该趟比较开始匹配的第一个字符，红色部分表示匹配失败的位置，绿色表示尚未进行比较的位置）：

第一趟比较：在i=2和j=2处出现不匹配，如下图中红色部分所示

第二趟比较：i不变，依然在主串的第2个字符处，子串向右滑动，相当于j回退，此趟比较从i=2和j=0处开始，在i=6和j=4处出现不匹配，如下图中红色部分所示

第三趟比较：i依然在主串的第6个字符处，子串向右滑动，此趟比较从i=6和j=1处开始，最终匹配成功

我们可以看到，只用3趟就可以完成匹配，而采用BF算法则要6趟才能完成。为什么可以这样移动呢？我们从第一趟比较的结果得知，主串的第2个字符为b，而子串的第一个字符为a，因此，因此可以直接将BF算法的第二趟比较省去，而直接进入第三趟比较，也就是KMP算法的第二趟比较，再往后面，通过该趟比较，我们又知道主串的第4、5、6个字符必然是bca，它们无须再与子串的第一个字符比较，这样便可以直接从i=6和j=1处进行比较。

这里的关键问题：每趟匹配过程中产生失配时，子串该向右滑动多远，换句话说，当主串的第i个字符和子串的第j个字符失配时，下一趟比较开始时，主串的第i个字符应该与子串的哪个字符再去比较。这个问题我们在后面讨论，我们先将KMP算法的代码给出，我们假设失配时，主串的第i个字符与子串中的第next[j]个字符进行比较，并令j=0时，即在第一个字符处适时，next[j]=-1,则那么我们可以写出KMP算法的代码如下：

/*
返回子串Ptn在主串Tag的第pos个字符后(含第pos个位置)第一次出现的位置，若不存在，则返回-1
采用KMP算法，这里的位置全部以从0开始计算为准，其中T非空，0<=pos<=Tlen
*/
int kmp_index(const string &Tag,const string &Ptn,int pos)
{
	int i = pos;  //主串当前正待比较的位置，初始为pos
	int j = 0;   //子串当前正待比较的位置，初始为0
	int Tlen = Tag.size();  //主串长度
	int Plen = Ptn.size();  //子串长度
	
	while(i
  
   = Plen)
		return i - Plen;
	else
		return -1;
}
  

前缀数组next的求解

以上代码很简单，也很容易理解，对照BF算法，并没有该几行代码，关键在于如何求next数组（也叫前缀数组），下面我们着重来看next数组的求法。

我们假设主串为“T0T1...Tn-1”,子串为“P0P1...Pm-1”在失配后，主串中的第i个字符应与子串中的第k（0

P0 P1 ... Pk-1 = Ti-k Ti-k+1 ... Ti-1

而我们由上一趟的比较，已经得到了如下匹配结果：

P0 P1 ... Pj-1 = Ti-j Ti-j+1 ... Ti-1

我们取其中的部分匹配结果，如下：

Pj-k Pj-k+1 ... Pj-1 = Ti-k Ti-k+1 ... Ti-1

比较第一个公式和第三个公式，我们便可以得出如下结果：

P0 P1 ... Pk-1 = Pj-k Pj-k+1 ... Pj-1

这样，所有的问题就转移到子串Ptn上了，因此next数组元素的值只与子串的形式有关，而与主串没有任何关系。如果在子串中存在满足上式的的两个子字符串，则在失配后，下一趟比较仅需从子串Ptn的第k个字符与主串Tag的第i个字符开始。于是可以令next[j]的表达式如以下三种情况所示：

（1）当j>0时，next[j] = Max{k|k满足 0

（2）当j=0时，next[j] = -1

（3）当j>0且又不存在满足 P0 P1 ... Pk-1 = Pj-k Pj-k+1 ... Pj-1 的k时，next[j] = 0