字符串匹配（一） -- 朴素匹配与 KMP 算法
1. 引言
软件算法中，最基础的算法要数排序和查找了，而字符串模式匹配算法可谓是基础中的基础，而最有名又最具代表性的字符串匹配算法要数 KMP 算法了，本文我们就来详细介绍一下 KMP 算法
2. 朴素匹配算法
最简单的算法就是朴素匹配算法了，所谓的“朴素匹配算法”指的就是人们常说的“暴力匹配算法”。 将我们的原字符串与模式串从第一个字符开始，依次向后比较，如果全部比较相同，则返回成功，如果某个字符不同，则从原串下一个字符开始，重新从模式串首个字符开始比较。
2.1. 算法代码
#include <stdio.h>
#include <string.h>
int strpos_pure(char *str, char *pattern) {
for (int i=0; i < strlen(str); ++i) {
int j = 0;
for (; j < strlen(pattern); ++j) {
if (i + j >= strlen(str)) {
return -1;
}
if (str[i + j] != pattern[j]) {
break;
}
}
if (j == strlen(pattern)) {
return i;
}
}
return -1;
}
int main() {
char str[20], pattern[20];
printf("please input the string:\n");
scanf("%s", str);
printf("please input the pattern:\n");
scanf("%s", pattern);
int pos = strpos_pure(str, pattern);
if (pos >= 0) {
printf("search success\n");
} else {
printf("search fail\n");
}
return 0;
}2.2. 时间复杂度
假设原字符串长度为 n，模式串长度为 m，在最坏的情况下，我们总共要位移 n - m + 1 次，而对于每次移位，都要进行 m 次比较，因此最坏情况下算法时间复杂度为 O(m*(n - m + 1))
3. KMP 算法
如果模式串为 ABCDE，我们通过上述的朴素字符串匹配算法与原字符串 ABCDFABCDE 进行匹配，假设经比较原字符串开始处的 ABCD 已经与模式串匹配，而 E 却不匹配，按照朴素匹配算法，我们接下来将比较原字符串 BCDFANBCDE 与模式串。 然而，我们清楚的知道，既然原字符串匹配了 ABCD，那么向后移动 1、2、3 位都是不可能匹配的，所以我们直接向后移动 4 位，将 ABCDE 与 FABCDE 进行比较就省去了 3 次比较过程。 我们能够一次性移动 4 位的原因是什么呢？是因为已匹配部分的字符串没有重复字符，如果已匹配字符串拥有重复字符，情况又会变得不一样。 假设我们需要比较 ABCABCABD 与模式串 ABCABD，那么首个不匹配的是模式串中下标为 5 的字符 D，我们是否可以直接后移 5 位 ，让原字符串的子串 CABD 与模式串 ABCABD 比较呢？显然是不行的，因为模式串中已匹配部分前后缀拥有相同的“AB”，此时，我们应该向后移动 3 位，让原字符串的子串 ABCABD 与我们的模式串 ABCABD 进行比较。 上述思想正是 KMP 算法的主要思想，只要理解了上述过程 KMP 算法就已经呼之欲出了。
3.1. 算法描述
按照上述介绍，假设模式串中首个不匹配元素的下标为 p，在模式串 0 ~ p-1 子串中，最长公共前后缀重合元素数为 q，那么此时后移步长为 p - q。 这样，只要在模式串与原串进行比较前，计算出模式串每个位置 x 前 0 ~ x-1 子串的最长公共前后缀重合元素数，我们就可以大幅向前移位，从而实现最大限度的减少比较次数，降低算法的时间复杂度了。 从而，我们的问题也就被转化为最长公共前后缀重合元素数的计算了。
3.2. 最长公共前后缀重合元素数计算
那么最长公共前后缀重合元素数怎么计算呢？ 下面我们以模式串 ABCDABD 为例，来计算最长公共前后缀重合元素数。
ABCDABD 各子串最长公共前后缀重合元素数 q
子串 | 前缀 | 后缀 | q |
|---|---|---|---|
A | - | - | 0 |
AB | A | B | 0 |
ABC | A,AB | C,BC | 0 |
ABCD | A,AB,ABC | D,CD,BCD | 0 |
ABCDA | A,AB,ABCD | A,DA,CDA,BCDA | 1 |
ABCDAB | A,AB,ABC,ABCD,ABCDA | B,AB,DAB,CDAB,BCDAB | 2 |
ABCDABD | A,AB,ABCD,ABCDA,ABCDAB | D,BD,ABD,DABD,CDABD,BCDABD | 0 |
通过上表我们可以总结出规律（假设模式串为 m，最长公共前后缀重合元素数数组为 next，我们需要计算 next[k]）：
- 若 k == 0，则 next[k] = 0
- 若 m[k] == m[next[k-1]]，则 m[k] = next[k-1] + 1
我们重点需要考虑一下，如果 m[k] != m[next[k-1]]，那么，我们要缩小判断范围，来查看此时的最大重合前后缀长度，根据 next 数组的定义，我们可以知道，m[0:next[k-1] - 1] 与 k 前面的 next[k-1] 个元素是完全重合的，因此，我们现在需要将范围缩小到 m[0:next[k-1]-2]，所以需要比较 m[next[k-1] - 2] 与 m[k]，于是有：
- 若 next[k-1] < 2，则 next[k] = 0
- 若 m[next[k - 1] - 2] == m[k]，则 next[k] = next[next[k-1]] + 1
- 若 m[next[k - 1] - 2] != m[k]，则令 j = next[k - 1] - 2 然后按照上述流程继续比较 m[next[j - 1] - 2] 与 m[k]
上面我们的 next 数组总是需要用下标 - 1，这样显得略微繁琐，那么如果我们将 next 数组中的所有元素右移，将 next[0] 设置为 -1，这样我们就可以简化上述流程：
#include <stdio.h>
#include <string.h>
void get_next(char *p,int *next) {
int p_len = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < p_len - 1) {
if (k == -1 || p[j] == p[k]) {
++k; ++j;
next[j] = k;
} else {
k = next[k];
}
}
}
int main() {
int next[20];
get_next("ABABCABABAC", next);
}3.3. next 数组求解进一步优化
我们利用上面的算法，针对 abab 这个模式字符串求解他的 next 数组为 [-1, 0, 0, 1] 当我们使用这个模式字符串来匹配原字符串 abacababc。
如上图所示，末尾的 b 与 c 不匹配，此时右移步长为 3 - 1 = 2。
我们看到，移位后紧接着判断失配位置仍然匹配失败，接着我们需要再次进行移位 1 + 1 = 2 位。 事实上，我们在第一次移位以前就可以通过比较原字符串失配位置上的字符与移位后模式串该位置上的字符来得到是否仍然失配的信息，从而将两次移位变成一次移位了。 代码改动非常简单：
#include <stdio.h>
#include <string.h>
void get_next(char *p,int *next) {
int p_len = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < p_len - 1) {
if (k == -1 || p[j] == p[k]) {
++k; ++j;
if (p[j] != p[k]) {
next[j] = k;
} else {
next[j] = next[k];
}
} else {
k = next[k];
}
}
}
int main() {
int next[20];
get_next("ABABCABABAC", next);
}3.4. 算法代码
#include <stdio.h>
#include <string.h>
void get_next(char *p,int *next) {
int p_len = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < p_len - 1) {
if (k == -1 || p[j] == p[k]) {
++k; ++j;
if (p[j] != p[k]) {
next[j] = k;
} else {
next[j] = next[k];
}
} else {
k = next[k];
}
}
}
int strpos_kmp(char *str, char *pattern) {
int next[strlen(pattern)];
get_next(pattern, next);
for (int i = 0; i < strlen(str); ++i) {
int j = 0;
for (; j < strlen(pattern); ++j) {
if (str[i + j] != pattern[j]) {
i += j - next[j] - 1;
break;
}
}
if (j == strlen(pattern)) {
return i;
}
}
return -1;
}
int main() {
char str[20], pattern[20];
printf("please input the string:\n");
scanf("%s", str);
printf("please input the pattern:\n");
scanf("%s", pattern);
int pos = strpos_kmp(str, pattern);
if (pos >= 0) {
printf("search success\n");
} else {
printf("search fail\n");
}
return 0;
}3.5. 时间复杂度
按照上述算法，如果某个字符匹配成功，模式串首字符的位置保持不动，仅仅是i++、j++；如果匹配失配，i 不变（即 i 不回溯），模式串会跳过匹配过的next [j]个字符。整个算法最坏的情况是，当模式串首字符位于i - j的位置时才匹配成功。 因此，对于原字符串长度 n，模式串长度 m，算法匹配过程最大时间复杂度为 O(n)，加上计算 next 的 O(m) 时间，整体时间复杂度为 O(m + n)，由于 m 一定小于 n，所以整体时间复杂度在最坏情况下仍然是 O(n)
4. 参考资料
《算法导论》。 https://blog.csdn.net/v\_JULY\_v/article/details/7041827。 https://zh.wikipedia.org/zh-hans/%E5%85%8B%E5%8A%AA%E6%96%AF-%E8%8E%AB%E9%87%8C%E6%96%AF-%E6%99%AE%E6%8B%89%E7%89%B9%E7%AE%97%E6%B3%95。
腾讯云开发者
