[数据结构与算法]《数据结构》—— 串的模式匹配算法

一、简单的模式匹配算法（BF算法）

在实际应用中我们常常能用到类似串的模式匹配，也称子串的定位操作。例如单词查找，百度搜索都是串的模式匹配操作。

字符串模式匹配： 在主串中找到与模式串相同的?串，并返回其所在位置。

• ?串——主串的?部分，?定存在；
• 模式串——不?定能在主串中找到。

例如：主串为：‘abaabaabcabaa’，模式串：‘baabc’；算出?串第?个字符的位置。

【逻辑分析】: 算出主串中有多少个子串， 模式串与子串进行匹配；子串与模式串从第一个开始匹配，当他们的第一个相等，就接着匹配下一个，知道模式串匹配成功或者失败，最后返回结果。
子串：{abaab,baaba,aabaa,abaab,baabc,aabca,bcaba,cabaa}；
模式串：baabc ；

易知：当匹配到第5个子串时，匹配成功，返回子串第一个字符的位置。在循环匹配中，模式串始终是从第一个字符开始匹配；而主串是当子串匹配不成功时+1,再匹配的。

在很多场景中，主串远比模式串长得多，即n>>m。
匹配成功的最好时间复杂度: O(m) ；
匹配失败的最好时间复杂度: O(n-m+1) = O(n-m)=O(n)；
匹配失败的最坏时间复杂度：O(n*m)。

int Index(SString S, SString T, int pos)
{
	//返回模式串T在主串S中第pos个字符之后第S一次出现的位置。若不存在，则返回值为0
	//其中，T非空，1≤pos≤StrLength(S)
	int i = pos;
	int j = 1;
	while(i<=S.length && j<=T.length)
	{
		if(S[i]==T[j])
		{
			++i;
			++j;
		} //继续比较后继字符
		else
		{
			i=i-j+2;
			j=1;
		} //指针后退重新开始匹配
	}
	if (j>T.length)
		return i-T.length;
	else
		return 0;
}

完整代码：

/***字符串匹配算法***/
#include<cstring>
#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255   		//用户可在255以内定义最长串长
typedef char SString[MAXSTRLEN+1];		//0号单元存放串的长度

Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T
	int i;
	if (strlen(chars) > MAXSTRLEN)
		return ERROR;
	else {
		T[0] = strlen(chars);	//char长度赋给T[0]
		for (i = 1; i <= T[0]; i++)
			T[i] = *(chars + i - 1);  //char的值赋给字符串T
		return OK;
	}
}

//算法4.1　BF算法
int Index(SString S, SString T, int pos)
{
	//返回模式T在主串S中第pos个字符之后第s一次出现的位置。若不存在，则返回值为0
	//其中，T非空，1≤pos≤StrLength(S)
	int i = pos;
	int j = 1;
	while(i <= S[0]&&j <= T[0])
	{
		if(S[i]==T[j])
		{
			++i;
			++j;
		} //继续比较后继字符
		else
		{
			i=i-j+2;
			j=1;
		} //指针后退重新开始匹配
	}
	if (j > T[0])
		return i - T[0];
	else
		return 0;
	return 0;
}//Index

int main()
{
	SString S;	//S串为主串
	StrAssign(S,"abaabaabcabaa") ;
	SString T;	//T串为模式串；
	StrAssign(T,"baabc") ;
	cout<<"主串和子串在第"<<Index(S,T,1)<<"个字符处首次匹配\n";
	return 0;
}

二、KMP算法

上面的BF算法中频繁的重复比较相当于模式串在不断地进行自我比较，导致其效率低下。我们不得不思考有没有更高校的方法。

我们不想要主串回溯操作，利用部分匹配直接跳转到还没进行匹配的字符那里。

next数组: 当模式串的第j个字符匹配失败时，令模式串跳到next[j]再继续匹配。

当子串和模式串不匹配时，主串指针i不回溯，模式串指针j=next[j]。

KMP算法，最坏时间复杂度 O(m+n)；其中，求 next 数组时间复杂度 O(m)，模式匹配过程最坏时间复杂度 O(n)。

/***字符串匹配算法***/
#include<cstring>
#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255 	//用户可在255以内定义最长串长
typedef char SString[MAXSTRLEN+1]; //0号单元存放串的长度

Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T
	int i;
	if (strlen(chars) > MAXSTRLEN)
		return ERROR;
	else {
		T[0] = strlen(chars);
		for (i = 1; i <= T[0]; i++)
			T[i] = *(chars + i - 1);
		return OK;
	}
}
//计算next函数值
void get_next(SString T, int next[])
{ //求模式串T的next函数值并存入数组next
	int i = 1, j = 0;
	next[1] = 0;
	while (i < T[0])
		if (j == 0 || T[i] == T[j]) 
		//根据模式串T，求出next数组
		{
			++i;
			++j;
			next[i] = j;
		}
		else
			j = next[j];
}//get_next

//KMP算法
int Index_KMP(SString S, SString T, int pos, int next[])
{ 	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
	//其中，T非空，1≤pos≤StrLength(S)
	int i = pos, j = 1;
	while (i <= S[0] && j <= T[0])
		if (j == 0 || S[i] == T[j]) // 继续比较后继字
		{
			++i;
			++j;
		}
		else //利?next数组进?匹配（主串指针不回溯）
			j = next[j]; // 模式串向右移动
	if (j > T[0]) // 匹配成功
		return i - T[0];
	else
		return 0;
}

int main()
{
	SString S;
	StrAssign(S,"aaabbaba") ;
	SString T;
	StrAssign(T,"abb") ;
	int *p = new int[T[0]+1]; // 生成T的next数组
	get_next(T,p);
	cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配\n";
	return 0;
}