字符串匹配算法是常用的算法,其中最有名的算法就是 kmp 算法和 AC 自动机. 另外介于这两个之间的 Trie 树.
一些概念字符串的匹配的场景一般是这样的,简单说就是一个大的字符串中有没有一个字符串匹配,我们把大的字符串叫做主串,而匹配最后小的字符串叫做模式串.
而字符串匹配算法就是模式串匹配主串.
BF 算法在了解 kmp 算法之前,先用最简单的暴力破解的手段,这种方式最简单也最直接.
代码语言：c复制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 开始.
时间复杂度和空间复杂度算法中时间复杂度和空间复杂度是一个此消彼长的,如果要降低时间复杂度,必然会提高空间复杂度,当然除非你写的代码很差...
算法原理我们计算的大概情况如下:
我们先计算出模式串的自我匹配情况:
我们这样计算,当模式串下标后一位字符不匹配的时候,我们需要怎么去移动字符串来保证时间复杂度最低.
所以我们可以先计算出模式串的这样的位置,如果不匹配直接移动.
代码语言：c复制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.
有了这样一个函数,那么我们进行匹配就比较简单了.
代码语言：c复制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 树.