字符串--KMP算法详细解析

字符串—KMP算法详细解析

一：概述

• 给定文本串text和模式串pattern，从文本串text中找出模式串pattern第一次出现的位置

• 最基本的字符串匹配算法

  • 暴力求解(Brute Force)：时间复杂度(m*n)

• KMP算法是一种线性时间复杂度的字符串匹配算法，它是对BF算法的改进

• 记：文本串长度为N，模式串长度为M

  • BF算法的时间复杂度为O(M*N)，空间复杂度为O(1)
  • KMP算法的时间复杂度O(M+N)，空间复杂度为O(M)

二：BF算法(暴力求解过程)

图解：

• 定义文本串和字符串

• 进行第一次比较

用模式串的第j个元素去和文本串的第(i+j)个元素进行比较，如果相等则 j = j+1，继续比较模式串的第j个元素和文本串的第(i+j)个元素继续比较。当j = 5时，模式串与文本串不匹配。如果发现不匹配，则 j=0，i = i+1，

• 进行第二次比较

用模式串的第j个元素(此时j为0)和文本串的第(i+j)个元素(此时i=1)开始匹配，发现 i = 1 和 j = 0时不匹配，则 j = 0，i = i + 1

• 进行第三次比较

用模式串的第j个元素(此时j为0)和文本串的第(i+j)个元素(此时i=2)开始匹配，如果相等则 j = j+1，继续比较模式串的第j个元素和文本串的第(i+j)个元素继续比较。发现当i = 8 和 j = 6时不匹配，则 j = 0，i = i + 1

依次类推，直至匹配完成。

代码实现：

int BruteForceSearch(const char* s,const char* p){
	int i = 0;  // 当前匹配到的原始串首位
	int j = 0;  // 模式串的匹配位置
	int size = (int)strlen(s);
	int psize = (int)strlen(p);
	while ((i < size) && (j < psize)){
		if(s[i+j] == p[j]) {  // 若匹配，则模式串匹配位置后移
			j++;
		}else {   // 不匹配。则对比下一个位置，模式串回到首位
			i++;
			j = 0;
		}
	}
	if(j >= psize)
		return i;
	return -1;
}

三：KMP算法

1. KMP算法过程解析

因为在暴力破解字符串时，会产生指针回溯的问题，即在发现字符不匹配时，j 指针会回到模式串的0位置。这样的话会大大影响程序的运行速率。

图解过程：

• 第一次比较时，当 j 指针移动到 j = 5时，发现字符不匹配，对此时对 j 指针前面的字符串进行前后缀的划分。前后缀的字符个数必须大于1且前后缀必须取最大字符串且不能为它本身。之后将前缀移到后缀的位置。

• 将模式串整体左移之后，可以发现，模式串 j 的指针左端与文本串一致，我们只需要从当前位置继续向右移动指针 j 即可，省去了指针回溯的操作。指针 j 继续向右移动，当移动到 j = 6时，发现字符不匹配，则继续划分前后缀，并将前缀字符放到后缀的位置上。当模式串匹配到正确字符或是模式串的位置超出了文本串时，停止移动，得出结果。此时，模式串正好匹配。

由上述过程可以看到，KMP算法处理字符串的匹配问题要比暴力处理字符串匹配简便的多。

2. KMP算法探究

​ 将前缀移动到后缀的位置也是有一个比较的过程的，不可能一下就移过去。我们这里先讲一下前缀移动到后缀位置的过程，以第二点中第一次移动为例，过程如下图所示：

​ 通过对以上过程的了解，我们可以明白字符串KMP匹配的基本原理。但按照算法和代码的角度看，在程序中字符串是无法像画图那样直接平移的。所以我们需要借助于next数组来存储模式串需要调整的位置或者说是索引，然后使 j 从数组中获取相应的值，从而通过修改 j 的位置来实现模式串的移动操作，避免比较操作。

​ (1)：next数组

​ 模式串中第 j 个位置与主串中第 i 个位置发生不匹配时，应从模式串中第next[j] 个位置与主串第 i 个位置重新开始比较。

​ 从上图中我们可以发现，当字符串的前缀移动到后缀的位置时，此时 j 指针指向字符串的第4个字符，即下一次比较要从模式串的第四个字符处进行比较。我们还可以发现，在 j 指针之前有3个字符是与文本串一样的。可以推测。前缀/后缀的长度 + 1 等于下一次比较的字符的索引

• next数组求法(手工求解版)

​ next[0]为0，为特殊标记，表示应从模式串第一个字符串与主串当前不匹配字符的下一个字符开始比较

​ next[j]的值为前缀或后缀的长度 + 1，其中前缀和后缀取最长的那一对。

​

​ 先看下标为1的的next的值，统一规定为0；接下来看下标为2的next的值，由于模式串的前缀和后缀为0，所以next为2的值为1；同理，下标为3的next的值为1；下标为4模式串的前缀或后缀的长度为1，所以下标为4的next值为2；以此类推，可或得所有next的值。

​

当 i 和 j 移动到第5个字符时，字符不匹配，此时next = 3，所以就使 j 指向模式串的第3个位置，则变为下图所示情况：

此时 i 和 j 指针所指的字符不相等，此时next = 1，所以就使 j 指向模式串的第1个位置，如下图所示

​

此时 i 和 j 指针所指的字符不相等，此时next = 0，next = 0 是特殊情况。当next = 0时，将指针 i 和j向右移动一位，移动后如图所示：

以下的过程按照上述过程进行即可。

(2)：数组构造代码

void getNext（Str substr, int next[]){
	int j=1, t=0;
	next[1] = 0;
	while(j<substr.length){
		if(t == 0 || substr.ch[j] == substr.ch[t]){
			next[j+1] = t + 1;
			++j;
			++t;
		}
		else
			t = next[t];
	}
}

3. KMP算法改进

我们以下面的一个模式串为例：

以上模式串的匹配步骤如下：

• 如果当j=5时，出现不匹配，j=next[j]=4
• j=4和j=5对应的字符时相等的，依然不匹配，此时，j=next[j]=3
• 不匹配，j=next[j]=2
• 不匹配，j=next[j]=1
• 不匹配，j=next[j]=0，执行i++1, j++1操作

由上面的例子我们可以看出，模式串的1-5位置相等且全为A，即j指针在每次移动后指向的字符与前一个字符相等。可以看出，我们在移动字符串时做了很多多余的步骤

改进思想：

​ 针对例子而言，我们只需将j=5的next数组值改为0就能拥有同样的效果，且可大大减少程序运行的步骤。所以KMP算法的改进主要集中在对数组的改进上，核心为修改数组的值使得通过数组取值可以直接跳到不相同字符上，改进后的数组称为nextval数组。

改进步骤：

​ 我们在遇到不匹配字符，j在向next[j]移动后，如果发现移动后的字符与前一个字符相等则忽略，如果不相等则将这个字符所对应的位置加入到不匹配字符对应的nextval数组位置。这样的话就可以跳过中间相同字符的比较，减少运行次数。

求解nextval数组

• 当j等于1时，nextval[j]赋值为0，作为特殊标记；

• 当j大于1时：

  若P_j不等于P_next[j]，则nextval[j]等于next[j]，即相同位置处，nextval的值与next的值相等

  若P_j等于P_next[j]，则nextval[j]等于nextval[next[j]]，即nextval数组中前后位置的值相等，保证他们能跳到同一位置

代码实现：

void getNextval（Str substr, int nextval[], int next[]){
	int j=1, t=0;
	next[1] = 0;
	nextval[1] = 0;
	while(j<substr.length){
		if(t == 0 || substr.ch[j] == substr.ch[t]){
			next[j+1] = t + 1;
			if (substr.ch[j+1] != substr.ch[next[j+1]])
				nextval[j+1] = next[j=1];
			else
				nextval[j+1] = nextval[next[j+1]];
			++j;
			++t;
		}
		else
			t = nextval[t];
	}
}

其实我们无需next数组也能实现nextval数组的创建，其中next[j+1]可以用t+1替换掉，代码如下：

void getNextval（Str substr, int nextval[]){
	int j=1, t=0;
	nextval[1] = 0;
	while(j<substr.length){
		if(t == 0 || substr.ch[j] == substr.ch[t]){
			if (substr.ch[j+1] != substr.ch[t+1])
				nextval[j+1] = t+1;
			else
				nextval[j+1] = nextval[t+1];
			++j;
			++t;
		}
		else
			t = nextval[t];
	}
}