C++串的模式匹配

在数据结构的学习过程中，继顺序表，链表，队列，栈之后的一个部分便是串。本质上串也是线性表的一种，其当然可以分为顺序存储结构与链式存储结构。它的一些接口也已经由STL中的<string.h>配备完全，需要时直接调用即可。
本文将主要介绍串的模式匹配部分，包括概念，Brute Force(BF)和KMP共三部分。因为我在学习和用C++实现KMP时，发现了诸多问题。所以本文将着重详解C++实现的KMkmP算法（包括生成next表）。

概念

所谓串的模式匹配，用白话讲，就是在主串(串S)中寻找第一次出现模式串(串T)的位置。找到返回T在S中的位置（T的首字符在S中的位置），找不到返回-1（有的喜欢返回 0，看各人喜好）。如下图所示，假设现有主串S和模式串T，那么模式匹配就是找T在S中位置，很容易便可发现T在S中的位置是3号位（字符串从0号位开始），所以这里return 3。下文中的BF和KMP算法便用于实现这种模式匹配。

下面讲解BF算法。

BF算法

Brute Force算法翻译过来可以为蛮力算法或者朴素算法，后简称BF算法。顾名思义，BF算法在思路上简单粗暴，很好理解。如图所示，BF算法的思路是：讲串T的每一个元素与串S的每一个元素进行比较，如果相等，串S和串T的位序分别向下移动一位，即，i++;j++;。如果元素不相等，则主串S回溯到本轮比较开始时的下一个位置，模式串T回溯到起始位置。比如：第一轮比较中，A!=D，则串S回溯到本轮比较开始位置的下一个位置，即位序1，即B元素。串T回溯到起始位置，即元素D。然后开始第二轮比较，发现B!=D，串S再次回溯到C，串T依然回到D。一直到第四轮比较，发现D=D，则i++;j++, 然后比较E=E，然后i++; j++;最后比较F=F，i++; j++。根据这个思路，主要问题就在于用数学表达式表达主串S每次比较失败后的回溯位置。关于为什么一定要讲这里是“回溯”，是因为我们设定，只要是元素对比成功，就会让主串S位序偏移，那么当后续元素比较不成功时，位序i 需要回归到原来位置的下一个位置，如果不“回溯”则会导致串S中有些元素被跳过。例如：假设下图中串S的5号位元素改为A，那么在最下一行的比较中, 由于D=D;E=E,主串i++了两次，那么现在i=5。但是在下一轮比较中，需要比较的是主串中4号位和模式串中的0号位，即，需要i=4!=5。所以需要用数学表达式来规定每次比较不成功时的回溯情况。
这里直接给出表达式：i=i-j+1（也有一些书给的时i=i-j+2，是因为他们的串位从1开始）; 其中，i是在一轮比较中被偏移了j次的主串位序，所以这里i=i-j。+1是因为要回到本轮比较开始时位序的下一位。
而模式串回溯直接归零：j=0;

下面给出c++代码实现

#include<iostream>
using namespace std;
#include <string>
int Index(string S, string T)
{
	int i = 0;
	int j = 0;//主串和模式串起始位置都是0
	int SLength = S.length();
	int TLength = T.length();//后续会详细解释这里
	while (i < SLength && j < TLength)
	{
		if (S[i] == T[j])
		{
			i++;
			j++;//与上面解释相同，比较成功时，位序++；
		}
		else
		{
			i = i - j + 1;
			j = 0;//比较不成功时主串和模式串回溯
		}
	}
	if (j == TLength) { return i - j; }
	else { return -1; }
}

代码比较简单，和上述讲解完全一致。但是这里着重要说的是这个位置：

为什么这里要单独设变量SLength和TLength而不是直接将S.length() 和L.length()放入到循环内？

第一个原因是：如果直接将S.length()放入循环体内，那么每一次while循环都会调用这个成员函数，造成资源浪费。这点很好理解。
那么我非要写成这样呢：

while (i < S.length() && j < T.length())
{
...
}

对不起，直接报错。

这是因为，string的成员函数length()返回值是 unsigned int，而变量 i 是int类型，所以这里告诉你，有符号不匹配。虽然这里int和unsigned int 的数值都是一个整形的长度，但是实际上在计算机底层这两个东西是完全不同的两个东西。简单来说，int类型因为可正可负数，所以计算机在分配给他的是32位的二进制空间，其最高位0/1代表了这个数字是正还是负。而unsigned int类型，由于没有符号，所以32位空间全部用于储存数字数据，而没有符号数据。所以造成了这两种类型混用会导致溢出问题。这里具体见这位大佬写的：深入解析unsigned int 和 int。比我讲的要详细。

那么要是搞一手强转呢？

while (i < (int)S.length() && j < (int)T.length())
{
...
}

在BF算法这个位置用这个强转是没有问题的，但是还是建议不要混用或者强转，因为在KMP中我用强转依然报错溢出，应该是底层还是有些问题。稳妥起见，这里用int 型接收一下效果比较好。

BF算法虽然简单易懂，但是他也有致命的缺陷，那就是时间复杂度高。

假设串S长度为n，串T长度为m。假设多趟匹配后匹配成功，那么最好的情况是：每趟中每一个串T第一个元素就匹配不上，此时平均时间复杂度为O(n)。最坏的情况是：每趟中，直到串T的最后一个元素匹配不上，此时平均时间复杂度为O(nm)。由于很多回溯是没有必要的，导致了高额的时间复杂度，所以大佬们想出了空间换时间的算法——KMP(Knuth-Morris-Pratt)算法。

KMP算法

算法概述

这里我借鉴B站up主 “地衣芽孢杆菌” 的“望江楼”例子。下面给出原视频链接，个人认为这位up主讲的很全面，很细，只不过是C语言实现的，我这里在他的基础上给出C++实现的方法和细节。
KMP算法实例详解(易懂)
先给出BF算法和KMP算法的直观区别。假设主串S为“望江楼，望江流，望江楼上望江流，江楼千古，江流千古”。模式串为“望江楼上望江江流”。我们人脑在处理这个问题很快就能发现，找不到模式串，程序结果应该返回-1。但是交给机器处理时，却需要算法来解决。假设这里依然用BF算法。如下图所示，根据BF的回溯原则，每次比对不成功（失配）时，主串回溯到本轮开始位置后一位，模式串回溯到开始位置。这就造成了很多本不需要比对的地方进行了多余的比对。比如第2、3轮，通过第1轮的比较已经知道了主串S前三个字符是“望江楼”，那么第二个字符就不是“望”，第三个字符也不是“望”。所以可以直接比对主串三号位“，”看它是不是“望”。再比如第10轮比较，在前一轮比较中已经比出了主串S[8-13]位的内容是“望江楼上望江”。那么图中的10-12轮比较都是没有意义的，直接比较T中2号位和主串14号位是否相同就可以。

按照上面的讲解，实际需要对比的内容如下图（图表不全，后面都是一样的，每次比T中“望”直到主串结束）：

可以看出，这种算法极大的减少了不必要的比对轮数，当然也降低了时间复杂度（后续分析）。而这种算法就是所谓的KMP算法。
KMP完整图示：

通过上图所示，至少可以总结出：
1、主串S没有进行过“回溯”，无论适配或者失配，主串S下标i一直进行i++;
2、模式串回溯位置并不是像BF算法中一样回溯到0，而是回溯到一个特定的位置。
3、在第8轮到第18轮中，KMP算法和BF算法运行方式完全相同。这说明KMP算法在这种串中字符变化较多，没有规律的时候并不能体现出他相较于BF算法的优越性。
下面继续讨论如何找出模式串回溯位置。

前缀和后缀

这里可以看出，重点是模式串回溯问题。那么模式串每次究竟回溯到哪才能保证既完成所有有效比对，又不浪费资源呢？这里要给出两个简单的概念：字符串的前缀和后缀：
举例说明：
假设现有字符串s=“abcab”;
那么字符串s的前缀有"a",“ab”,“abc”,“abca"和"abcab”。其中真前缀为"a",“ab”,“abc”,“abca”。即不包括自身。
同理，字符串s的后缀有"b",“ab”,“cab”,“bcab"和"abcab”。其中真后缀为"b",“ab”,“cab”,“bcab”。即不包括自身。

接下来看例子中的第6轮和第7轮。可以发现，在第6轮比较到“江”字失配后，主串S没有进行偏移，继续比对主串中14号位“流”这个位置。
但是模式串进行了回溯。那么回溯到哪呢？这里我们再把这部分按照BF算法展开，看看BF算法是怎么做的。通过对比不难发现，KMP比BF算法多比对了三轮，这个之前也有讲过。但是在BF算法中，第10轮实际上是从对比主串中12位的“望”开始的，而KMP算法是从对比主串中14位的“流”开始的，也就是直接让过了对比模式串开头的“望江”，直接比对主串的“流”和模式串的“楼”。

进一步归纳总结可以发现，模式串中在第六轮比对中失配的字符“江”前面的字符串（子串）为“望江楼上望江”，而这里可以发现，“望江”是这个“望江楼上望江”子串的真前缀，同时也是真后缀。并且是最大长度的真前缀和真后缀，即长度为2。而模式串正好回溯到这个2号位（第2+1=3个字符）位置，也就是最大相等真前后缀的后一位，即“楼”。那么可以总结出：失配时模式串回溯到失配字符前的子串的最大相等真前后缀长度的位置。

求解next表

那么现在对于模式串每个不同位置失配时回溯的位置确定的方法如上述，现再举一个例子。
如下图，假设现有模式串"abcdabad"。求解每个位置失配时回溯的位置。

假设在0号位失配，那么“a”前没有子串，所以回溯到它自身，即回溯到0号位；
假设在1号位失配，那么"b"前的子串"a"没有真前后缀，所以失配后还要回溯到0号位。
假设在2号位失配，那么"c"前的子串"abc"没有相等的真前后缀，所以失配后回到0号位。
同理，从3，4号位失配时，其前面的子串没有相等真前后缀，所以失配后回溯到0号位。
假设在5号位失配，不难发现5号位前面的子串的相等的真前后缀为"a"，长度为1，所以失配后回溯到
1号位的字符"b"；
假设在6号位失配，同理于5号位，其前子串相等真前后缀位"ab"，所以失配后回溯到2号位"c"；
假设在7号位失配，同理，失配后回溯到1号位"b"。
结果如下图所示：

在KMP算法中，模式串不同位置失配时回溯位置由next表记录，上面的分析过程叫做手动推算next表。
当然，我们不可能所有的都要用人去推算next表。还是要依靠算法。
这里我们可以分析一下，这个next表究竟是怎么推算出来的。根据上述的概念，生成next表的过程本质上就是在找每个位置前的子串的最大相等真前后缀的长度。那么其实也就是拿模式串的真前缀和模式串的真后缀进行比对。也就是和自身进行模式匹配。现假设用BF方法进行自身模式匹配。由上面的例子已知串0号位和1号位的next表值一定位0，我们要找2号位前的子串的相等真前后缀，所以从1号位开始比较。匹配图示如下：

不难看出：
1号位失配，也就证明了2号位前的子串的头"a"不等于尾"b"；所以2号位next表值为0；
2号位失配，也就证明了3号位前的子串的头"a"不等于尾"c"；所以3号位next表值为0；
3号位失配，也就证明了4号位前的子串的头"a"不等于尾"b"；所以4号位next表值为0；
4号位匹配，也就证明了5号位前的子串的头"a"等于尾"a"；所以5号位next表值为1；
5号位匹配，也就证明了6号位前的子串的头"ab"等于尾"ab"；所以6号位next表值为2；
注意，这里4号位和5号位是连续匹配，而不是下一轮从头开始比较的匹配。
6号位匹配，也就证明了7号位前的子串的头"a"等于尾"a"；所以7号位next表值为1；
上述分析和手动填写next表部分完全一致。
剔除不必要的比较：
可以看出这里和KMP的思想完全一致：作为主串的模式串没有回溯，作为模式串的模式串按照next表回溯。
并且当发生匹配时有：

next[i+1]=next[i]+1;
//因为next[i]=j；//比如next[5]=2=j这里我不太会用图片描述了，看不懂的话去看开头那个视频解释; 
//所以也可以写成
next[i+1]=j+1;
i++;j++;//两个串向后偏移一位

不匹配时，作为模式串的模式串按照next表回溯：

j=next[j];

到这里，next表生成的核心已经讲解完毕，下面附上代码：

	int length = T.length();
	int* next = new int[length];
	int i = 0; int j = -1;
	next[0] = -1;
	while (i < length - 1)//i要比length少一位，因为我们循环里是给next[i+1]赋值
	{																																	
		if (j == -1 || T[i] == T[j])//这里要注意，j==-1一定要放在前面，放在后面编译器会先判断T[i] == T[j]，由于上面复制了j=-1，会令编译器崩溃。							
																		
		{
			next[i + 1] = next[i] + 1;									/
			i++; j++;
			//pro版
			//i++;j++;
			//next[i] = ((T[i] == T[j]) ? next[j] : j);
		}
		else
		{
			j = next[j];
		}
		
	}
	return next;
};

可以看到，为了避免出现死循环，令next[0]=-1而不是0。大家可自行带入next[0]=0;并且if判断没有j=-1的入口情况。

KMP实现

生成好next表后，直接按照KMP算法概述中讲解的理论来写代码：

int IndexKMP(string S, string T)
{
	int* next = GenNext(T);
	int i = 0; int j = 0;
	int SLength = S.length();
	int TLength = T.length();
	while (i < SLength && j < TLength)
	{
		if (j == -1 ||S[i] == T[j])//匹配后两串偏移
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];//不匹配模式串回溯
		}
	}
	delete []next;//释放堆区数据
	return (j == TLength) ? i - j : -1;
}
int main()
{
	string S;
	S = "abcde";
	string T;
	T = "bcd";
	cout << IndexKMP(S, T) << endl;
	system("pause");
	return 0;
}

很容易可以分析出，KMP算法的平均时间复杂度为O(n+m)，相比于BF算法的O(nm)来说提升很大，用空间换时间。

至此C++串的模式匹配（BF,KMP详解）已经讲解完毕，貌似我的语文能力不太能够支撑我把这个东西讲清楚，大家可以拿我的文字和B站那个视频对着看，但愿对各位有所帮助。