串的模式匹配问题（含BF算法，KMP算法）

#include<bits/stdc++.h>
using namespace std;

//获得的下标 
int Index_BF(string s, string t) {
	int i = 0, j = 0;
	int slen = s.length();
	int tlen = t.length();
	for(; i < slen && j < tlen; i++, j++) {
		if(s[i] != t[j]){
			i = i - j; 
			j = -1;
		}
	}
	if(j == tlen)
		return i-tlen;
	return -1;
}

int main() {
	string s, t;
	cout << "请输入主串：" << endl;
	cin >> s;
	cout << "请输入模式串：" << endl;
	cin >> t;
	int ans = Index_BF(s, t);
	if(ans == -1)
		cout << "主串中没有模式串" << endl;
	else	//对下标加一则是逻辑位序
		cout << "模式串在主串中的位置是从第 " << ans + 1 << " 个元素开始的" << endl; 
	return 0; 
}

BF算法时间复杂度

若 n 为主串长度，m 为模式串长度，最坏情况是

主串前面 n – m 个位置都部分匹配到子串的最后一位，即这 n – m 位各比较了 m 次
最后 m 位也各比较了1次

总次数为:

(n – m) * m + m = (n – m + 1) * m

若

m << n

，则算法复杂度

O(n * m)

KMP算法

KMP算法介绍

KMP算法是一种字符串匹配算法，是由D.E.Knuth，J.H.Morris和V.R.Pratt提出的。其核心是利用字符串匹配失败后的的信息从而减少字符串与模式串的匹配次数从而提高字符串匹配的效率。

KMP算法设计思想

假设主串为s=”ababcabdabcabca”、模式串为p=”abcabc”，指针i、j分别指示主串和模式串所比较字符的位序号。

在第一趟匹配中，由于
$s_{0}=p_{0}$
,
$s_{1} = p_{1}$
,
$s_{2}\neq p_{2}$
,因此i=2,j=2;
按照之前的思路，我们应当修改i为1，j为0后再次进行比较。但由于
$p_{0}\neq p_{1}$
,
$s_{1}=p_{1}$
,因而
$p_{0}\neq s_{1}$
,所以此时不必从i为1处进行匹配，而只需匹配
$s_{2}$
和
$p_{0}$
;
在第三趟匹配中，由于
$s_{7}\neq p_{5}$
,显然此时有，
$s_{2}s_{3}s_{4}s_{5}s_{6}=p_{0}p_{1}p_{2}p_{3}p_{4}$
。因为
$p_{0}\neq p_{1}$
,
$p_{0}\neq p_{2}$
,所以
$p_{0}$
无需与
$s_{3}$
和
$s_{4}$
进行比较，而只需匹配
$s_{5}$
和
$p_{0}$
；又因为
$s_{0}s_{1}=p_{3}p_{4}$
,所以
$p_{0}p_{1} = s_{5}s_{6}$
,这两次比较也可以通过前次匹配的信息来略过；
通过以上的分析，我们不难发现，我们可以利用模式串自身的信息来计算模式串匹配失败后下一次所要匹配的位置，而主串的比较位置不需要回退。
当某次匹配失败时，有
$s_{i}\neq p_{j}$
那么
$s_{i-j}s_{i-j+1}....s_{i-1}$
=
$p_{0}p_{1}...p_{j-1}$
。如果在模式串中存在这样的k，使得
$p_{0}p_{1}...p_{k}$
=
$p_{j-k-1}p_{j-k}...p_{j-1}$
,那么在下一次匹配时，我们便只需匹配
$p_{k}$
和
$s_{i}$
。特别地，当k=0时，我们应当匹配
$p_{0}$
和
$s_{i}$
。(k应当使得
$p_{0}$
…
$p_{k}$
最长)

通过以上的分析，我们可以知道其实该算法的关键在于获取一个next数组，通过该数组来记录模式串中各个位置的最长前缀子串从而避免重复匹配的出现。也就是说模式串每次开始匹配的位置由模式串本身来决定。

next数组构建

我们不妨假设每次模式串开始的匹配的位置为k，j为模式串中某一字符所在的位序号。那么我们可以使用next[j] 来表示
$p_{j}$
所要开始匹配的位置（p为模式串）。

初始时，定义next[0] = -1,next[1] = 0;
设next[j] = k,那么有
$p_{0}p_{1}...p_{k-1}$
=
$p_{j-k}p_{j-k+1}...p_{j-1}$
,k为满足此等式的最大值。接下来我们需要计算的是next[j+1]的值。
如果
$p_{k}$
=
$p_{j}$
,那就意味着
$p_{0}p_{1}...p_{k-1}p_{k}$
=
$p_{j-k}p_{j-k+1}...p_{j-1}p_{j}$
成立。此时，我们可以得到next[j+1] = k+1。
如果
$p_{k}$
$\neq$
$p_{j}$
，那么next[j+1]的计算便成为了新的模式匹配过程。我们可以怎样理解呢？对于前缀子串
$p_{0}p_{1}...p_{k-1}$
，令 k’=next[k](该值已经记录在了next数组中)。那么有这样的两个等式:
$p_{0}p_{1}...p_{k'-1}$
=
$p_{k-k'}p_{k-k'+1}...p_{k-1}$
$p_{k-k'}p_{k-k'+1}...p_{k-1}$
=
$p_{j-k'}p_{j-k'+1}...p_{j-1}$
进一步，有
$p_{0}p_{1}...p_{k'-1}$
=
$p_{j-k'}p_{j-k'+1}...p_{j-1}$
。通过以上分析，当出现不匹配的情形时，我们应当前缀子串的匹配位置回退到k’处（k’=next[k]）。如果
$p_{k'}$
=
$p_{j}$
,那么next[j+1]=k’+1;否则，应当将前缀子串的匹配位置继续回退直到其与
$p_{j}$
匹配。特别地，当k’=0,且
$p_{0}\neq p_{j}$
时，next[j+1] = 0。

建立完next数组，便可以来完成KMP算法的构建了。

KMP算法代码实现

#include<bits/stdc++.h>
using namespace std;

//求Next数组  
void GetNext(string t, int next[]) {
	int i = 1, j = 0, tlen = t.length();
	next[0] = -1, next[1] = 0;
	while(i < tlen) {
		if(!j || t[i] == t[j])
			next[++i] = ++j;
		else
			j = next[j];
	}
}

//获得的下标  
int Index_KMP(string s, string t) {
	int tlen = t.length();
	int slen = s.length();
	int next[tlen + 5];
	int i = 0,j = 0;
	GetNext(t, next);
	while(i < slen && j < tlen) {
		if (j == -1 || s[i] == t[j]) 
			i++, j++;
		else j = next[j];
	}
	if (j == tlen)
		return i - tlen;
    else  
		return -1; 
}

int main() {
	string s, t;
	cout << "请输入主串：" << endl;
	cin >> s;
	cout << "请输入模式串：" << endl;
	cin >> t;
	int next[t.length() + 1];
	int ans = Index_KMP(s, t);
	if(ans == -1)
		cout << "主串中没有模式串" << endl;
	else	//对下标加一则是逻辑位序
		cout << "模式串在主串中的位置是从第 " << ans + 1 << " 个元素开始的" << endl; 
	return 0; 
}

KMP算法的改进

KMP算法与BF算法对比起来虽然有了巨大的优化，但KMP算法还可以变得更优。

例如：

S：a a a a a b a a a a a c 主串：正文串

T：a a a a a c 子串：模式串

这个例子中当 ‘b’ 与 ‘c’ 不匹配时应该 ‘b’ 与 ’c’ 前一位的 ‘a’ 比,这显然是不匹配的。’c’ 前的 ’a’ 回溯后的字符依然是 ‘a’ 。

我们知道没有必要再将 ‘b’ 与 ‘a’ 比对了，因为回溯后的字符和原字符是相同的，原字符不匹配，回溯后的字符自然不可能匹配。但是 KMP 算法中依然会将 ‘b’ 与回溯到的 ‘a’ 进行比对。这就是我们可以改进的地方了。我们改进后的 next 数组命名为：nextval 数组。KMP 算法的改进可以简述为：

如果 a 位字符与它next值指向的 b 位字符相等，则该 a 位的 nextval 就指向 b 位的nextval 值，如果不等，则该 a 位的 nextval 值就是它自己 a 位的 next 值。

KMP算法代码实现（优化版）

#include<bits/stdc++.h>
using namespace std;

//由模式串t求出nextval值
void GetNextval(string t,int nextval[]) {
	int tlen = t.length();
	int i = 0,j = -1;
	nextval[0] = -1;
	while (i < tlen) {
		if(j == -1 || t[i] == t[j]) {	
			i++;j++;
			if (t[i] != t[j])
				nextval[i] = j;
           	else
				nextval[i] = nextval[j];
		}
		else
			j = nextval[j];    	
	}
}

//获得的下标  
int Index_KMP(string s, string t) {
	int tlen = t.length();
	int slen = s.length();
	int nextval[tlen + 5];
	int i = 0,j = 0;
	GetNextval(t, nextval);
	while(i < slen && j < tlen) {
		if (j == -1 || s[i] == t[j]) 
			i++, j++;
		else j = nextval[j];
	}
	if (j == tlen)
		return i - tlen;
    else  
		return -1; 
}

int main() {
	string s, t;
	cout << "请输入主串：" << endl;
	cin >> s;
	cout << "请输入模式串：" << endl;
	cin >> t;
	int next[t.length() + 1];
	int ans = Index_KMP(s, t);
	if(ans == -1)
		cout << "主串中没有模式串" << endl;
	else	//对下标加一则是逻辑位序
		cout << "模式串在主串中的位置是从第 " << ans + 1 << " 个元素开始的" << endl; 
	return 0; 
}

KMP算法时间复杂度

设主串长为 n ，模式串长为 m

求 next 数组的时间复杂度为

O(m)

，

在KMP算法中，主串的下标无需回退，因此比较次数最多为

n – m + 1

，

因此 KMP 算法的时间复杂为

O(m + n)

。

原文链接：https://blog.csdn.net/m0_63330233/article/details/121077897

串模式匹配问题算法介绍

算法目的

算法应用

算法种类

BF算法

BF算法介绍

BF算法设计思想

BF算法代码实现