KMP模式匹配算法

目录

1.串的简单模式匹配——BF

2.KMP算法思想

3.模式串next数组及计算

4.KMP算法

5.next数组的缺陷和改进

1.串的简单模式匹配——BF

串的模式匹配就是子串定位操作，给定两个串s="s₀s₁.....sₙ₌₁"和t="t₀t₁.....tₘ₌₁"（其中n和m分别是串t和串s的长度），在主串s中寻找子串t的过程称为模式匹配，t称为模式。如果在s中找到等于t的子串，则匹配成功，返回t在s中的首次出现的下标位置；否则匹配失败，返回-1.

下面介绍蛮力（BF）模式匹配算法。算法的基本思想：

从主串s中下标为0的字符开始，与模式串t中下标为0的字符进行比较，若相同，则继续逐个比较s和t中的后续字符；若不同，则从主串s中下标为1的字符开始，与模式串t中下标为0的字符进行比较。以此类推，重复上述过程，若t中字符全部比较完，则说明匹配成功；否则匹配失败。

设主串s="ababcabcacb"，模式t="abcac"

最好情况的时间复杂度O(n+m)

最坏情况的时间复杂度O(n×m)

BF算法简单但效率低，KMP算法对BF算法的改进之处在于取消了主串的回溯，从而一定程度上了算法效率

2.KMP算法思想

分析BF算法的执行过程，造成BF算法慢的原因是回溯，即在某趟的匹配过程失败后，对于串s要回到本趟开始字符的下一个字符，串t要回到首字符，而这些回溯是不必要的

在第3趟匹配过程中，s₂~s₅和t₀~t₃是匹配成功的，s₆≠t₄匹配失败，因此有了第4趟，其实这一趟是不必要的，因为在第3趟中有s₃=t₁，而t₀≠s₃，就有t₀≠s₃。同样第5趟也没必要，进一步分析第6趟中的第一对字符s₅和t₀也是多余的，因为在第6趟的比较可以从第二对字符s₆和t₁开始进行。这就是说，在第3趟匹配失败后，指针i不动，而是将模式串t向右“滑动”，用t1“对准”s6继续进行匹配。这样的处理方法指针i是无回溯的。

某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置k上，使得tk对准si继续向右进行

如果模式串中满足式"t₀ t₁....tₖ₌₁"="tⱼ₌ₖ tₖ₌ⱼ₊₁.....tⱼ₋₁"的子串存在，即模式中的前k个字符与模式中tj字符前面的k个字符相等时，模式t就可以向右滑动使tₖ和sᵢ对准，继续向右进行比较

3.模式串next数组及计算

模式中的每一个tⱼ都对应一个k值，用next[j]表示tⱼ对应的k值，next数组定义如下：

 首先，求最长前缀表，比如：

abcab的最长前缀是2

abcd的最长前缀是0

abcabc的最长前缀是3

以下图数组为例，下标从0开始，首先把前缀表的第一位赋值为0

 然后将p写成如下形式，即将p[0]~p[n](1~8)写出，分别计算最长前缀

 然后将结果填入

 敲黑板！

上图并不是next数组，而是个前缀表prefix，但是离next数组很近了！只需将prefix数组的最后一个值即p[8]去掉，将p[0]前面加一个-1再整体后移一位，就得到next数组了！

源代码

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;

void prefix_table(char p[], int prefix[], int l) {
	prefix[0] = 0;
	int i = 1;
	int len = 0;
	while (p[i] != 0) {
		if (p[len] == p[i]) {
			len++;
			prefix[i] = len;
			i++;
		} else {
			if (len > 0) {
				len = prefix[len - 1];
			} else {
				prefix[i] = len;
				i++;
			}
		}

	}
}

int main() {
	int n = 9;
	char p[] = {"ABABCABAA"};
	int prefix[9];
	prefix_table(p, prefix, n);
	for (int i = 0; i < n; i++) {
		cout << prefix[i] << endl;
	}
	return 0;
}

运行结果

 4.KMP算法

举个例子，设主串s=“ababcabcacb”和模式串t="abcac"来说明KMP算法匹配过程

模式串t="abcac"的next数组值如下：

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
const int MaxSize = 255;  // 串的最大长度

// 串的定长顺序存储结构
typedef struct {
	char ch[MaxSize + 1]; // 存储串的一维数组
	int length;   // 串的当前长度
} SString;

// 初始化
void Init(SString &S, char s[]) {
	S.length = strlen(s);
	for (int i = 1; i < S.length + 1; i++) {
		S.ch[i] = s[i - 1];
	}
	S.ch[0] = S.length;
}
/*

// 通过计算返回字串T的next数组值
void get_next(String T, int *next)
{
    int i, j;
    i = 1; j = 0;
    next[1] = 0;
    while (i<T.ch[0])  // 此时T[0]表示串T的长度
    {
        if(j == 0 || T.ch[i] == T.ch[j]) // T[i]表示后缀的单个字符, T[j]表示前缀的单个字符
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];  // 若字符不相同，则 j 值回溯
    }
}
int Index_KMP(SString S, SString T, int pos) {
	int i = pos; // i 用于表示主串S当前下标值，若pos不为1，则从pos位置开始匹配
	int j = 1;  // j 用于表示字串T当前下标值
	int nextval[255]; // 定义一next数组
	get_nextval(T, nextval); // 对串T进行分析，得到nextval数组
	while (i <= S.ch[0] && j <= T.ch[0]) { // 当 i 小于S的长度且 j 小于T的长度时，循环继续
		if (j == 0 || S.ch[i] == T.ch[j]) { // 两字符相等则继续，与朴素算法增加了 j=0 的判断
			++i;
			++j;
		} else {    // 指针 j 后退，重新开始匹配
			j = nextval[j];   // j 退回合适的位置，i 值不变
		}
	}
	if (j > T.ch[0]) {
		cout << i - T.ch[0] << endl;
		return i - T.ch[0];
	} else {
		cout << "匹配失败！" << endl;
		return 0;
	}
}

int main() {
	SString S;
	SString T;
	int pos;
	char s[MaxSize + 1], t[MaxSize + 1];
	cout << "请输入主串S：" << endl;
	cin >> s;
	Init(S, s);
	cout << "请输入模式串T：" << endl;
	cin >> t;
	Init(T, t);
	cout << "请输入你想要在S中开始匹配的位置 pos：" << endl;
	cin >> pos;
	cout << "匹配结果：";
	Index_KMP(S, T, pos);
	return 0;
}

5.next数组的缺陷和改进

克服不必要重复比较的方法是对next数组的修正，在算法中求得next[j]=k后，要继续判断tₖ和tⱼ是否相等，若相等还要使next[j]=next[k]。修正后的next数组称为nextval数组

例如，已知主串s="aaabaaaab"和模式串t="aaaab"，利用KMP算法进行模式匹配

根据KMP算法，当i=3,j=3时，s₃≠ t₃，由next[j]的指示还需要进行i=3、j=2，i=3、j=1，i=3、j=0等三次比较。实际上，模式串中下标为0、1、2的字符和下标为3的字符都相等，就不需要和主串中 下标为3的字符进行比较，可以将模式一起向右滑动4个字符的位置直接进行i=4、j=0的字符比较

计算nextval的具体过程：

• 第一位的nextval值必定为0，第二位如果与第一位不同则为0，相同则为-1
• 第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则第三位的nextval值为第一位的nextval值，为-1
• 第四位的next值为2，那么将第四位和第二位进行比较，均为a，相同，则第三位的nextval值为第二位的nextval值，为-1
• 第五位的next值为3，那么将第五位和第三位进行比较，不同，则第五位的nextval值为其next值，为3

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;

void getnextval(char *t, int nextval[]) {
	int j, k, m;
	j = 0;
	k = -1;
	m = strlen(t);
	nextval[0] = -1;
	cout << "nextval[0]=" << nextval[0] << endl;
	while (j < m - 1) {
		if (k == -1 || t[j] == t[k]) {
			j++;
			k++;
			if (t[j] != t[k])
				nextval[j] = k;
			else
				nextval[j] = nextval[k];
			cout << "nextval[" << j << "]=" << nextval[j] << endl;
		} else
			k = nextval[k];
	}
}

int main() {
	int n = 5;
	char t[] = {"aaaab"};
	int nextval[5];
	getnextval(t, nextval);
	for (int i = 0; i < n; i++) {
		cout << nextval[i] << endl;
	}
	return 0;
}