字符串模式匹配算法——KMP算法_字符串匹配算法kmp

目录

前言

BF算法

基本思路

过程图解

代码实现

不足之处

改进方式

KMP算法

基本思路

数组next[ ]

字符串最长相等前后缀

数组next[ ]的形成原理

数组next[ ]的作用 

求next数组的代码

 KMP算法的过程图解

代码实现

KMP算法的改进

基本思路

数组nextval[ ]

数组nextval[ ]的形成原理

改进后KMP算法的过程图解

代码实现

---

前言

字符串是一种常见的数据结构，它由一个字符序列组成，可以被视为字符的数组或列表。每个字符都有一个对应的索引位置，允许对字符串进行访问、修改和操作。对于字符串而言，寻找字符串中子串的位置是最重要的操作之一，查找子串位置的操作通常称为模式匹配。在模式匹配中，通常将主串称为目标串，而将子串成为模式串。

本文仅介绍两种模式匹配算法，BF算法和KMP算法。

规定：本文记目标串s = "abcaabbabcabaab" , 模式串t = "abcabaa" .

           用i遍历目标串s的字符，用j遍历模式串中的字符.

BF算法

BF算法，又称简单匹配算法，

基本思路

从目标串s的第一个字符开始，与模式串t的第一个字符比较，若字符匹配，则继续逐个比较后续字符；否则，从目标串回溯到第二个字符重新与模式串的第一个字符进行比较。以此类推，当目标串s的第i个字符开始与模式串t的每个字符逐个比较，若匹配成功，则返回位置i；否则目标串回溯至第i + 1个字符与模式串t逐个比较。

过程图解

代码实现

int BF(string s, string t)
{
	int i = 0, j = 0;
	while (i < s.size() && j < t.size())
	{
		//比较当前字符是否相等
		if (s[i] == t[i])
		{
			//相等时，i,j后移一位，接着比较下一位字符
			i++;
			j++;
		}
		else
		{
			//不等时，i回溯，j重置为0，重新开始遍历
			i = i - j + 1;
			j = 0;
		}
	}
	//判断模式串是否遍历完
	if (j >= t.size())
		//遍历完则返回t在s中的位置
		return (i - t.size());
	else
		//否则返回-1
		return (-1);
}

 说明：s.size()与t.size()表示目标串s和模式串t的长度，代码中以数组s[i]、t[i]的形式访问字符串中的字符.

不足之处

该算法虽然简单且易于理解，但效率不高，主要原因是目标串s中i在若干个字符比较后，若有一个字符与其不匹配，就需要进行回溯（即i = i - j + 1）。这种反反复复的回溯会大量增加程序的运行时间，而且很多运算是不必要进行的。在最好情况下时间复杂度为O(n)，即子串的n个字符正好等于主串的前n个字符，而最坏的情况下时间复杂度为O(m*n)。

改进方式

BF算法的高时间复杂度主要是由于其目标串s的回溯，倘若我们可以减少目标串指针的回溯次数，便可以降低其时间复杂度，而接下来的KMP算法就实现了这一需求。

KMP算法

Knuth-Morris-Pratt字符串查找算法，简称为“KMP算法”，常用于在一个文本串S内查找一个模式串P的出现位置，KMP算法由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的。KMP算法与BF算法相比有较大的改进，主要是消除了目标串指针的回溯，从而使算法的效率在某种程度上提高了。

基本思路

KMP算法是通过增加空间复杂度来减小时间复杂度。

当目标串s与模式串t进行匹配时，遇到字符不相匹配时，保持目标串s的指针i不变，将模式串t根据一个特殊的数组next[]进行回溯。

数组next[ ]

数组next[ ]是用来记录模式串t的指针j在某一位置时其之前遍历过的字符区段中最长相等的前后缀。

说明：next[i]=j的含义是：下标为i 的字符前的字符串最长相等前后缀的长度为j。

字符串最长相等前后缀

示例：以模式串t = "abcabaa"为例

前缀集合 = {a,ab,abc,abca,abcab,abcaba}

后缀集合 = {a,aa,baa,abaa,cabaa,bcabaa}

则其最长相等前后缀为：a

注意：前缀和后缀不能等于字符串本身。 

数组next[ ]的形成原理

依旧以模式串t = "abcabaa"为例

当模式串t的指针j位于不同位置时

规定：next[0] = -1.

数组next[ ]的作用 

当目标串s与模式串t进行匹配，部分过程如下：

当匹配到i = 4时，目标串s的字符与模式串t的字符已经无法匹配， 此时模式串t的指针回溯 j = 1

由next数组可知，next[4] = 1,故可知当目标串s字符与模式串t字符不匹配时，模式串t的指针进行回溯，即 j = next[ j ]。

数组next[ ]的作用主要有两点：

1. next[j]的值表示下标为j的字符前的字符串最长相等前后缀的长度。
2. next[j]的值为当字符串不匹配时，模式串指针应该回溯的位置下标。

求next数组的代码

int GetNext(string t, int next[])
{
	int j = 0, k = -1;
	//规定：第一个字符前无字符串，故给值-1；
	next[0] = -1;
	//因为数组的最大下标为t.size()-1,但字符串的前缀与后缀不能与本身相等
	//所以遍历时只能取到t.size()-2;
	while (j < t.size() - 1)
	{
		if (k == -1 || t[j] == t[k])
		{
			//当字符匹配时，目标串s和模式串t的指针同时后移一位
			j++;
			k++;
			next[j] = k;
		}
		else
		{
			//当字符不匹配时，模式串t的指针进行回溯
			k = next[k];
		}
	}
}

 KMP算法的过程图解

代码实现

int KMPPIndex(string s, string t)
{
	int next[MaxSize], i = 0, j = 0;
	//获取模式串t的next数组
	GetNext(t, next);
	while (i < s.size() && j < t.size())
	{
		//判断指针是否指向第一个字符或比较当前字符是否相等
		if (j == -1 || s[i] == s[j])
		{
			//指针不在第一个字符时，i,j后移一位再进行比较
			//相等时，i,j后移一位，接着比较下一位字符
			i++;
			j++;
		}
		else
		{
			//字符不匹配时，回溯模式串t的指针j
			j = next[j];
		}
		//判断模式串是否遍历完
		if (j >= t.size())
			//遍历完则返回t在s中的位置
			return (i - t.size());
		else
			//否则返回-1
			return (-1);
	}
}

KMP算法的改进

KMP算法是否可以进一步改进呢？

回看KMP算法过程图解时，我们发现在第一次匹配与第二次匹配中，模式串t的指针进行回溯时依旧没有改变目标串s中的'a'字符与模式串t中的'b'字符进行比较。倘若我们可以避免这种重复的比较，是否就进一步优化了KMP算法。

基本思路

当目标串s与模式串t进行匹配时，遇到字符不相匹配时，保持目标串s的指针i不变，将模式串t根据一个特殊的数组next[]进行回溯，若回溯后的字符与当前字符一样，则跳过当前回溯直接进行下次回溯，即构建一个特殊的数组nextval[ ] 代替next[ ] 数组的功能。

通过减少模式串t的指针的回溯次数来优化KMP算法。

数组nextval[ ]

数组nextval[ ] 用于记录改进后的KMP算法的模式串t的指针回溯的下标。

数组nextval[ ]的形成原理

规定：nextval[ 0 ] = -1. 

说明：当字符不匹配时，模式串t的指针 j 将进行回溯。若回溯后的字符与回溯前一致，则nextval [ j ] =  next [ next [ j ] ] ,若不一致，则nextval [ j ] = next [ j ]。

改进后KMP算法的过程图解

代码实现

//求取nextval[ ]
int GetNext(string t, int nextval[])
{
	int j = 0, k = -1;
	//规定：第一个字符前无字符串，故给值-1；
	nextval[0] = -1;
	//因为数组的最大下标为t.size()-1,但字符串的前缀与后缀不能与本身相等
	//所以遍历时只能取到t.size()-2;
	while (j < t.size() - 1)
	{
		if (k == -1 || t[j] == t[k])
		{
			//当字符匹配时，目标串s和模式串t的指针同时后移一位
			j++;
			k++;
			//判断指针回溯前字符是否相等
			if (t[j] != t[k])
				//不相等时，回溯到该位置
				nextval[j] = k;
			else
				//相等时，跳过当前回溯
				nextval[j] = nextval[k];
		}
		else
		{
			//当字符不匹配时，模式串t的指针进行回溯
			k = nextval[k];
		}
	}
}
 
//KMP
int KMPPIndex(string s, string t)
{
	int nextval[MaxSize], i = 0, j = 0;
	//获取模式串t的next数组
	GetNext(t, nextval);
	while (i < s.size() && j < t.size())
	{
		//判断指针是否指向第一个字符或比较当前字符是否相等
		if (j == -1 || s[i] == s[j])
		{
			//指针不在第一个字符时，i,j后移一位再进行比较
			//相等时，i,j后移一位，接着比较下一位字符
			i++;
			j++;
		}
		else
		{
			//字符不匹配时，回溯模式串t的指针j
			j = nextval[j];
		}
		//判断模式串是否遍历完
		if (j >= t.size())
			//遍历完则返回t在s中的位置
			return (i - t.size());
		else
			//否则返回-1
			return (-1);
	}
}

本文仅是本人作为初学者的理解，若有不正确或不全面的方面，还望各位批评指正。