今日学习总结--模式匹配算法

模式匹配算法

所谓模式匹配就是在一个主串s中找到子串t的位置，对于复杂的字符串，那么使用怎样的方式去查找就显得尤其重要了。

1、朴素的模式匹配算法
为什么称为朴素呢？因为简单易理解，大家都可以想到，实现起来也相对简单，主要完全可以实现功能。

思路：主串s和子串t都从第一位开始比较，如果相等则比较第二位…如果其中某一位不相等了，则将s回退到i-j+1位置（每次比较一旦遇到不相同，就从开始位置后移一位），j回退到0.（子串又一次从头开始比较）

如下述例子
图1：当比较到第4位发现不相等后，i = i - j +1—> 1
而j = 0; 右开始了新一轮的比较
图2：比较主串第2位的时候，发现不相等，i = i - j +1—> 2
…经过一系列的失败匹配后，移动到了图5
图5:主串从第5开始匹配子串，然后发现全部匹配成功，结束。

今日学习总结--模式匹配算法
以下为实现代码：

#include<iostream>

using namespace std;
//返回子串t在主串t中第pos个字符之后的位置；若不存在，函数返回0
//t非空，1≤pos≤s.size()

int Index(string s, string t){
	int i = 0;
	int j = 0;//两个串都是要从头开始比较
	while (i < s.size() && j < t.size()){
		//一旦有一个串等于了size（）要么就是t到头 说明找到了   如果是s到头 说明没有找到
		if (s[i] == t[j]){
			i++;
			j++;
		}
		else{
			i = i - j + 1;//主串位置从开始比较位置后移一位
			j = 0;
		}
	}
	if (j >= t.size()){
		return i - t.size() + 1; //只有子串到头了 才说明找到了
	}
	else{
		return 0;
	}
}

int main()
{
	string s = "goodgoogle";
	string t = "google";
	cout << Index(s, t) << endl;
	return 0;
}

分析一下时间复杂度：

（最坏）具体如
主串是s=“00000000000000000000000000000000000000000000000001”
子串是 t=“00001” 则在比较的过程中，每次都要判断到第五位才能发现不相等然后又在主串后移一位之后继续比较5次…如此重复，则事件复杂度是O((n-m+1)*m)

基于人类如果在比较的时候，发现前面那些位都是相同的只有某一位不同，就不会在比较前面的，而是直接从不同的那一位开始比较。
因此出现了主串位置不回溯，那么子串应该如何选择最恰当的位置以减少比较次数呢？

2、KMP模式匹配算法

首先假设是这种情况：
今日学习总结--模式匹配算法
因此发现不相同之后，就直接从不相同的位置以及子串第一位开始再次比较。

上面的例子具有特殊性，因为也有可能出现很多子串后面是有相同部分的。
今日学习总结--模式匹配算法
这样，是不是就省去了第4 第5 两个位置的重复比较。

因此，KMP的关键在于比较之前预先遍历子串形成一个next数组

next数组作用：在于当子串和主串出现不相等之后，可以参考next数组，知道j将要回溯到的位置是多少。

如何构建next数组？
首先，第一位的next值为0，第二位的next值为1。联系next数组的功能很容易想到为什么要如此设计前两位的值；
其次，求解每一位的next值时，根据前一位进行比较，使用前一位和他指向的next数组值对应下标的值进行比较，如果相等，那么+1就是当前所求位的next值；
如果出现不等的情况，那就用前一位的next值指向的位置的值的next值指向的位置的值进行比较，如果相等，那么当前所求的next值就是前前位值的next值+1；
如果一直没有找到，当到头之后，所求位值的next就是1.

具体看例子：
例如有一个子串（也叫做模式串） t = "a b a a b c a c " 相应的next值应该是 0 1 1 2 2 3 1 2

今日学习总结--模式匹配算法

有了以上分析相信应该掌握了求解next数组的思想，那么通过下述例子练习一下看看：

由此可以实现KMP算法代码

KMP代码

#include<iostream>
using namespace std;

//通过计算，返回子串的next数组
void get_next(string t, int *next)
{
	int i, j;
	i = 1;
	j = 0;
	next[1] = 0;
	while (i<t.size() - 1)
	{
		if (j == 0 || t[i] == t[j])		//t[i]表示后缀的单个字符，t[j]表示前缀的单个字符
		{
			i++;
			j++;
			next[i] = j;
		}
		else
			j = next[j];			//若字符不相同，则j值回溯
	}

}

//返回子串t在主串t中第pos个字符之后的位置；若不存在，函数返回0
//s[0]和t[0]应该保存字符串的长度，这里我们随意保存一个字符#

int Index_KMP(string s, string t)	
{
	int i = 1;					
	int j = 1;					
	int next[255];					//定义一个next数组
	get_next(t, next);				//对串做分析，得到next数组

	while (i < s.size() && j < t.size())		//若i小于s的长度且j小于t的长度，循环继续
	{
		if (j == 0 || s[i] == t[j])		
		{
			i++;
			j++;
		}
		else					//当发现主串和子串不相等后，主串i位置不回溯，子串通过next数组得到一个合适的位置
			j = next[j];
	}
	if (j >= t.size())
		return i - t.size() + 1;
	else
		return 0;
}

int main()
{
	string s = "#goodgoogle";
	string t = "#google";
	cout << Index_KMP(s, t) << endl;
	return 0;
}

针对以上KMP的一点改进

分析例子：
主串 s = “aaaabcde” 子串 t = “aaaaax” 如果我们使用之前的方法，求出next是 012345 然后我们就会发现执行的过程是
今日学习总结--模式匹配算法
比较时候，当你发现第5位不相等之后，查找next数组拿到j = next[5] = 4, 然后就出现了第2步，接着依然不相等…就有了2 3 4 5 这几步无效的操作。
实际上发现2 3 4 5这几个位置上的值是和第1个位置上的值相等之后，完全可以用第一个位置的next值替代后面的next值，也就是说，不相等之后，直接将j回退到第一位开始比较。

改进后的KMP算法

void get_nextval(string t, int *nextval)
{
	int i, j;
	i = 1;
	j = 0;
	nextval[1] = 0;
	while (i<t.size() - 1)
	{
		if (j == 0 || t[i] == t[j])		
		{
			i++;
			j++;
			if (t[i] == t[j])		//若当前字符与前缀字符相等
			{
				nextval[i] = nextval[j];//将前缀字符的nextval值赋值给nextval在i位置上的值
			}
			else
				nextval[i] = j;		//当前的j为nextval在i位置上的值
		}
		else
			j = nextval[j];			//不相等，j回溯
	}
}

仅仅调整一下 get_nextval函数即可

到此，实现了KMP。分析时间复杂度为得到next数组的n和后面匹配时候的m，则O(m+n)

今日学习总结--模式匹配算法

模式匹配算法

相关推荐