OJ须知:
- 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间(中值5*10e8)。在竞赛中,一般认为计算机1秒能执行 5*10e8 次计算。
时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11
时间复杂度排序:o(1) < o(log2n) < o(n) < o(nlog2n) < o(n^2) < o(n^3) < o(2^n) < o(2^n) < o(3^n) < o(n!)
目录
字符串匹配算法
KMP算法
引出next数组
求next数组的练习
用手 + 看
用数学式
next数组的优化
引入nextval数组
复杂度分析
字符串匹配算法
BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T 的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和 T的第一个字符,依次比较下去,直到得出最后的匹配结果。BF算法是一种蛮力算法。(百度百科)
接下来我们就将这段晦涩难懂的话,举一个例子:S:"ababcabcd",T:"abcd"。
- 相等时:
- 不相等时:
思路代码化展示:
#include <cstdio>
#include <cassert>
#include <cstring>
int BF(const char* str, const char* sub)
{
assert(str != nullptr && sub != nullptr);
if (str == nullptr || sub == nullptr)
return -1;
int i = 0;
int j = 0;
int strLen = strlen(str);
int subLen = strlen(sub);
while (i < strLen && j < subLen)
{
if (str[i] == sub[j])
{
i++;
j++;
}
else
{
//回退
i = i - j + 1;
j = 0;
}
}
if (j >= subLen)
return i - j;
return -1;
}
int main()
{
printf("%d\n", BF("ababcabcdabcde", "abcd"));
printf("%d\n", BF("ababcabcdabcde", "abcde"));
printf("%d\n", BF("ababcabcdabcde", "abcdef"));
return 0;
}
KMP算法
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1]。(百度百科)
#区别:KMP 和 BF 唯一不一样的地方在,主串的 i 并不会回退,并且 j 也不会移动到 0 号位置。
- 首先举例,为什么主串不回退?
如果按照BF算法,那么必须i变为第二个字符,将变为第一个字符。但是我们可以知道都比到这个位置了,那么从 i 向前和 j 向前的字符串一定是相等的。
而根据KMP算法就是,先分析短的子字符串。
是不是有一对,以j - 1结尾的字符串和0开头的子字符串相等。而根据i 向前和 j 向前的字符串一定是相等可以知道。
看似是巧合,但这就是核心!因为此时我们并不需要将i移动,并且已经比较了一段。
而现在的问题就是: j 如何知道,它该移到哪一个指定的位置?
引出next数组
KMP 的精髓就是 next 数组:也就是用 next[j] = k;来表示,不同的 j 来对应一个 K 值, 这个 K 就是你将来要移动的 j 要移动的位置。
而 K 的值是这样求的:
- 规则:找到匹配成功部分的两个相等的真子串(不包含本身),一个以下标 0 字符开始,另一个以 j-1 下标 字符结尾。
- 不管什么数据 next[0] = -1; next[1] = 0; 在这里,我们以下标来开始,而说到的第几个第几个是从 1 开始。
#一句话:next[0] = -1,next[1] = 0,此后找以0开头、j - 1结尾的两字串相等的长度。
求next数组的练习
-
用手 + 看
练习 1:对于 "ababcabcd",求其的 next 数组?
练习 2:对于 "abcabcabcabcdabcde",求其的 next 数组?
-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0
#Tip:增加一定只会 +1
-
用数学式
到这里相信大家对如何求next数组应该问题不大了,那么接下来的问题就是:已知next[i] = k;怎么求next[i+1] = ?;。
首先假设:next[i] = k 成立,那么就有这个式子成立: P[0]...P[k-1] = P[x]...P[i-1];
并且由于长度的相等,所以x也是可以推算而出的: k - 1 - 0 = i - 1 - x ,所以带入x: P[0]...P[k-1] = P[i-k]...P[i-1]; 。
到这一步:我们再假设如果 P[k] == P[i]; 我们可以得到 P[0]...P[k] = P[i-k]..P[i]; 那这个就是 next[i+1] = k+1;
再来看看: Pk != Pi 的时候。
融汇贯通的理解:(为什么以此方式回退?)
逻辑思维转换图
#一句话:k一直回退,直到找到p[i] == p[k],否者k = -1,然后next[所求] = k + 1。
//KMP算法
#include <cstdio>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
int KMP(std::string str, std::string sub)
{
if (str.size() == 0 || sub.size() == 0)
return -1;
std::vector<int> next(sub.size(), 0);
// 利用数学式求next
next[0] = -1, next[1] = 0;
for (int i = 1; i < sub.size() - 1; i++)
{
int k = next[i];
while (sub[k] != sub[i])
{
k = next[k];
if (k == -1) break;
}
next[i + 1] = k + 1;
}
int j = 0;
int i = 0;
while(i < str.size())
{
// j == -1 一开始就匹配失败了,那i++;j++;正好是sub重新开始,str下一个
if (j == -1 || str[i] == sub[j])
{
i++;
j++;
if (j == sub.size()) return i - j;
}
else j = next[j];
}
return -1;
}
int main()
{
printf("%d\n", KMP("ababcabcdabcdeebcd", "ebcd"));
printf("%d\n", KMP("ababcabcdabcde", "abcde"));
printf("%d\n", KMP("ababcabcdabcde", "abcdef"));
return 0;
}
next数组的优化
在上述的处理方式会出现下列情况。
这一步一步回退不好,最好的就是一步就跳到第一个a,然后直接 -1 + 1 = 0,于是便有了next数组的优化,引入一个nextval数组。
引入nextval数组
nextval数组的求法:
- 回退到的位置和当前字符一样,就写回退那个位置的nextval值。
- 如果回退到的位置和当前字符不一样,就写当前字符原来的next值。
//KMP算法
#include <cstdio>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
int KMP(std::string str, std::string sub)
{
if (str.size() == 0 || sub.size() == 0)
return -1;
std::vector<int> next(sub.size(), 0);
std::vector<int> nextval(sub.size(), 0);
// 利用数学式求next
next[0] = -1, next[1] = 0;
nextval[0] = -1;
for (int i = 1; i < sub.size() - 1; i++)
{
int k = next[i];
// 求nextval
if (sub[k] == str[i]) nextval[i] = nextval[i - 1];
else nextval[i] = next[i];
while (sub[k] != sub[i])
{
k = nextval[k];
if (k == -1) break;
}
next[i + 1] = k + 1;
}
int j = 0;
int i = 0;
while(i < str.size())
{
// j == -1 一开始就匹配失败了,那i++;j++;正好是sub重新开始,str下一个
if (j == -1 || str[i] == sub[j])
{
i++;
j++;
if (j == sub.size()) return i - j;
}
else j = next[j];
}
return -1;
}
int main()
{
printf("%d\n", KMP("ababcabcdabcdeebcd", "ebcd"));
printf("%d\n", KMP("ababcabcdabcde", "abcde"));
printf("%d\n", KMP("ababcabcdabcde", "abcdef"));
return 0;
}
利用nextval优化求next效果:文章来源:https://www.toymoban.com/news/detail-457107.html
文章来源地址https://www.toymoban.com/news/detail-457107.html
复杂度分析
- 时间复杂度:O(m+n),srt字符串长m、sub字符串长n。
- 空间复杂度:O(n)。
到了这里,关于【算法思维】-- KMP算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!