字符串匹配算法
原创字符串匹配算法
原创
字符串匹配算法是常用的算法,其中最有名的算法就是 kmp 算法和 AC 自动机. 另外介于这两个之间的 Trie 树.
一些概念
字符串的匹配的场景一般是这样的,简单说就是一个大的字符串中有没有一个字符串匹配,我们把大的字符串叫做主串,而匹配最后小的字符串叫做模式串.
而字符串匹配算法就是模式串匹配主串.
BF 算法
在了解 kmp 算法之前,先用最简单的暴力破解的手段,这种方式最简单也最直接.
int bf(char* a, int n, char* b, int m){
for(int i = 0; i < n - m; i++){
int j = 0;
while(j < m){
if(*(a + i) != *(b + j)){
break;
}
j++;
}
}
// 如果可以匹配 j == m
if(j == m){
return i;
}
return -1;
}这个暴力求解的语法理解起来不难,就是下标不断遍历主串,然后不断匹配从下标不断从 0 开始匹配,最后判断有没有匹配过来.
KMP 算法
暴力算法自然耗时很长,那么从哪里去优化这个算法呢, 其实就是每次匹配的时候,为什么每次都从 0 开始匹配,能不能先算出来一个值,如果我模式串某个下标不匹配我直接跳到这个下标位置,没有必要从 0 开始.
时间复杂度和空间复杂度
算法中时间复杂度和空间复杂度是一个此消彼长的,如果要降低时间复杂度,必然会提高空间复杂度,当然除非你写的代码很差...
算法原理
我们计算的大概情况如下:
我们先计算出模式串的自我匹配情况:
我们这样计算,当模式串下标后一位字符不匹配的时候,我们需要怎么去移动字符串来保证时间复杂度最低.
所以我们可以先计算出模式串的这样的位置,如果不匹配直接移动.
int* getNexts(char* b, int m){
int next[m];
next[0] = -1;
int k = -1;
for(int i = 1; i < m; i++){
while(k != -1 && b[k+1] != b[i]){
k = next[k];
}
if(b[k + 1] == b[i]){
k++;
}
next[i] = k;
}
return next;
}上述计算其实使用了动态规划的算法思想,其中我们假定 nextk ,如果 k + 1 和 i 位置字符相同,那么 nexti = k+1, 而如果不匹配,我们可以想见,那么 nexti 肯定小于 k ,那么我们肯将下标回溯到 nextk.
有了这样一个函数,那么我们进行匹配就比较简单了.
int kmp(char* a, int n,char* b, int m){
int * next = getNexts(b, m);
int j = 0;
for(int i = 0; i < n; i++){
while(j > 0 && a[i] != b[j]){
j = next[j - 1] + 1;
}
if(a[i] == b[j]){
j++;
}
if(j == m){
return i - m + 1;
}
}
return -1;
}KMP 算法使用大概如此,后续还有 Trie 树和 AC 自动机, 其中一个负责单模式字符串匹配,一个可以实现多模式字符串匹配,AC 自动机就不再实现,下一篇我们实现 Trie 树.
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
