做区位分析底图的网站,网站怎么加内容,赞皇建站建设,自动生成ui界面KMP 算法是一个快速查找匹配串的算法#xff0c;它的作用其实就是本题问题#xff1a;如何快速在「原字符串」中找到「匹配字符串」。 在朴素解法中#xff0c;不考虑剪枝的话复杂度是 O(m∗n) 的#xff0c;而 KMP 算法的复杂度为 O(mn)。
KMP 之所以能够在O(mn) 复杂度内…KMP 算法是一个快速查找匹配串的算法它的作用其实就是本题问题如何快速在「原字符串」中找到「匹配字符串」。 在朴素解法中不考虑剪枝的话复杂度是 O(m∗n) 的而 KMP 算法的复杂度为 O(mn)。
KMP 之所以能够在O(mn) 复杂度内完成查找是因为其能在「非完全匹配」的过程中提取到有效信息进行复用以减少「重复匹配」的消耗。
你可能不太理解没关系我们可以通过举个例子来理解 KMP。
1. 匹配过程
在模拟 KMP 匹配过程之前我们先建立两个概念
前缀对于字符串 abcxxxxefg我们称 abc 属于 abcxxxxefg 的某个前缀。后缀对于字符串 abcxxxxefg我们称 efg 属于 abcxxxxefg 的某个后缀。
然后我们假设原串为 abeababeabf匹配串为 abeabf
先看看如果不使用 KMP会如何进行匹配不使用 substring 函数的情况下。 首先在「原串」和「匹配串」分别各自有一个指针指向当前匹配的位置。 首次匹配的「发起点」是第一个字符 a 。显然后面的 abeab 都是匹配的两个指针会同时往右移动黑标。 在都能匹配上 abeab 的部分「朴素匹配」和「KMP」并无不同。
直到出现第一个不同的位置红标 接下来正是「朴素匹配」和「KMP」出现不同的地方
先看下「朴素匹配」逻辑
将原串的指针移动至本次「发起点」的下一个位置b 字符处(遍历原串)匹配串的指针移动至起始位置。尝试匹配发现对不上原串的指针会一直往后移动直到能够与匹配串对上位置。
如图 也就是说对于「朴素匹配」而言一旦匹配失败将会将原串指针调整至下一个「发起点」匹配串的指针调整至起始位置然后重新尝试匹配。 这也就不难理解为什么「朴素匹配」的复杂度是O(m∗n) 了。 然后我们再看看「KMP 匹配」过程
首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在则跳转到「前缀」的下一个位置继续往下匹配 跳转到下一匹配位置后尝试匹配发现两个指针的字符对不上并且此时匹配串指针前面不存在相同的「前缀」和「后缀」这时候只能回到匹配串的起始位置重新开始。
到这里你应该清楚 KMP 为什么相比于朴素解法更快 因为 KMP 利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配。 因为 KMP 的原串指针不会进行回溯没有朴素匹配中回到下一个「发起点」的过程。 第一点很直观也很好理解。 我们可以把重点放在第二点上原串不回溯至「发起点」意味着什么
其实是意味着随着匹配过程的进行原串指针的不断右移我们本质上是在不断地在否决一些「不可能」的方案。当我们的原串指针从 i 位置后移到 j 位置不仅仅代表着「原串」下标范围为 [i,j) 的字符与「匹配串」匹配或者不匹配更是在否决那些以「原串」下标范围为 [i,j)为「匹配发起点」的子集。
2. 分析实现
我们分析一下复杂度。如果严格按照上述解法的话最坏情况下我们需要扫描整个原串复杂度为 O(n)。同时在每一次匹配失败时去检查已匹配部分的相同「前缀」和「后缀」跳转到相应的位置如果不匹配则再检查前面部分是否有相同「前缀」和「后缀」再跳转到相应的位置 … 这部分的复杂度是 O(m^2)因此整体的复杂度是 O(n * m^2)而我们的朴素解法是 O(m * n)O(m∗n) 的。
说明还有一些性质我们没有利用到。
显然扫描完整原串操作这一操作是不可避免的我们可以优化的只能是「检查已匹配部分的相同前缀和后缀」这一过程。
再进一步我们检查「前缀」和「后缀」的目的其实是「为了确定匹配串中的下一段开始匹配的位置」。
同时我们发现对于匹配串的任意一个位置而言由该位置发起的下一个匹配点位置其实与原串无关。
举个 例子对于匹配串 abcabd 的字符 d 而言由它发起的下一个匹配点跳转必然是字符 c 的位置。因为字符 d 位置的相同「前缀」和「后缀」字符 ab 的下一位置就是字符 c。
可见从匹配串某个位置跳转下一个匹配位置这一过程是与原串无关的我们将这一过程称为找 next 点。
显然我们可以预处理出 next 数组数组中每个位置的值就是该下标应该跳转的目标位置 next 点。
当我们进行了这一步优化之后复杂度是多少呢
预处理 next 数组的复杂度未知匹配过程最多扫描完整个原串复杂度为 O(n)。
因此如果我们希望整个 KMP 过程是 O(m n)的话那么我们需要在 O(m)的复杂度内预处理出 next数组。
所以我们的重点在于如何在 O(m)复杂度内处理处 next 数组。
3. next 数组的构建
接下来我们看看 next 数组是如何在 O(m)的复杂度内被预处理出来的。
假设有匹配串 aaabbab我们来看看对应的 next 是如何被构建出来的。 这就是整个 next 数组的构建过程时空复杂度均为 O(m)。
至此整个 KMP 匹配过程复杂度是 O(m n)的。
4.算法实现
python代码
def build_next(patt):计算 Next 数组next [0] # next 数组(初值元素一个0)prefix_len 0 # 当前共同前后缀的长度i 1while i len(patt):if patt[prefix_len] patt[i]:prefix_len 1next.append(prefix_len)i 1else:if prefix_len 0:next.append(0)i 1else:prefix_len next[prefix_len - 1]return nextdef kmp_search(string, patt):next build_next(patt)i 0 # 主串中的指针j 0 # 子串中的指针while i len(string):if string[i] patt[j]: # 字符匹配 指针后移i 1j 1elif j 0: # 字符失配根据 next 跳过字串前面的一些字符j next[j - 1]else: # 子串第一个字符就失配i 1if j len(patt): # 匹配成功return i - jstring ABABABCAA
patt ABABC
ind kmp_search(string, patt)
print(ind)acwing 831 KMP字符串
#include iostream
#include stringusing namespace std;const int N 10010;
const int M 100010;
int ne[N];//把每一个点为终点的最长相同前缀和后缀的长度存在里面
char s[M], p[N];int main() {int n, m;cin n p 1 m s 1;ne[1] 0;//这里从1开始for (int i 2, j 0; i n; i) {while (j p[j 1] ! p[i]) j ne[j];if (p[j 1] p[i]) j;ne[i] j;}for (int i 1, j 0; i m; i) {while (j s[i] ! p[j 1]) j ne[j];if (s[i] p[j 1]) j;if (j n) {j ne[j];cout i - n ;}}return 0;
}5.总结
KMP 算法的应用范围要比 Manacher 算法广Manacher 算法只能应用于「回文串」问题相对比较局限而「子串匹配」问题还是十分常见的。
背过这样的算法的意义在于相当于大脑里有了一个时间复杂度为 O(n) 的 api 可以使用这个 api 传入一个原串和匹配串返回匹配串在原串的位置。
