字符串匹配算法：KMP算法_kmp算法最坏情况下比较次数

---

KMP (Knuth–Morris–Pratt) 算法是一种改进的字符串匹配算法，它的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

题目：给定一个 T 字符串和一个 P 字符串，在 T 字符串中找出 P 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例：

T="ABABCABABDE", P="ABABDE"
1

---

暴力匹配

遍历字符串 T，将其中的每个字符与 P 的首字符进行比较，

1. 如果 T[i] == P[0]，遍历 P，判断 P 中的每个字符是否与 S 中对应位置的字符相等。若都相等，返回 i；否则进行下一步。
2. 如果不相等，递增 i。再进行步骤 1，直至 T 遍历结束。

下面是C++代码实现：

int strMatch(string T, string P){
	int n = T.size();
	int m = P.size();
	if(m==0) return 0;	// P为空字符串
	for(int i=0; i<n-m+1; ++i){
		int j=0;
		int k=i;
		for(; j<m; ++j, ++k){
			if(T[k]!=P[j]) break;
		}
		if(j==m){
			return i;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最坏情况下，比较次数为 $(n-m+1)\cdot m$。当 $n>>m$ 时，时间复杂度为 $O(nm)$。

对于示例，使用暴力匹配的过程如下，每次都从 P 的首个字符进行比较：

(1)ABABCABABDE
   ABABDE
(2)ABABCABABDE
    ABABDE
(3)ABABCABABDE
     ABABDE
(4)ABABCABABDE
      ABABDE
(5)ABABCABABDE
       ABABDE
(6)ABABCABABDE
        ABABDE
1
2
3
4
5
6
7
8
9
10
11
12

---

KMP算法

如果使用 KMP 算法进行字符串匹配，可以利用匹配失败后的信息。对于给定示例，其过程如下：

(1)ABABCABABDE i=0
   ABABDE      j=0
(2)ABABCABABDE i=4
     ABABDE    j=2
(3)ABABCABABDE i=4
       ABABDE  j=0
(4)ABABCABABDE i=5
        ABABDE j=1
1
2
3
4
5
6
7
8

上面的 i 和 j 分别表示每一轮开始时，先比较 T[i] 和 P[j]。
可以看到，从第(1)步知道，T 中的第二个 AB 子串不能与 P 的第二个 AB 子串匹配。
因为 P 中有两个 AB 子串，所以在第(2)步中，直接将 T 中的第二个 AB 子串与 P 的第一个 AB 子串进行匹配，再比较后续对应的字符。

构造 next 数组

next[i] 表示 P[0…i - 1] 子串的最长公共前缀后缀的长度。令 next[0] = -1。

对于示例，next 数组对应的值如下，其中第 1 列表示 next[i] 的值，第 2 列表示 P 的子串：

-1
0  A
0  AB
1  ABA
2  ABAB
0  ABABD
1
2
3
4
5
6

构造 next 数组的C++代码实现如下：

void getNext(string& s, vector<int>& next){
	int n = s.size();
	if(n==0) return;
	next.resize(n);
	next[0] = -1;
	int t = -1;
	int i = 0;
	while(i<n-1){
		if(t==-1 || s[t]==s[i]){
			++t;
			++i;
			next[i] = t;
		}
		else{
			t = next[t];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

KMP算法实现

解题思路：

• 求出 next 数组。
• 初始时，令 i=j=0，i 和 j 分别指向 T 和 P 中的字符。
  ①若此时 T 和 P 中的字符匹配，则继续比较它们的下一位，即 ++i, ++j；
  ②否则 j=next[j]，因为此时，根据 next 数组的性质，T[i-j, i-1] 和 P[0, j-1] 这两个子串是匹配的。

C++代码实现如下：

int strMatch(string& T, string& P){
	int n = T.size();
	int m = P.size();
	if(m==0) return 0;
	vector<int> next;
	getNext(P, next);
	
	int i=0, j=0;
	while(i<n && j<m){
		if(j<0 || T[i]==P[j]){
			++i;
			++j;
		}
		else{
			j = next[j];
		}
	}
	if(j==m){	// 匹配成功
		return i-j;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

KMP 算法的时间复杂度为 $O(n+m)$，空间复杂度为 $O(m)$。

---

刷题题解目录