字符串匹配-BF算法和KMP算法

声明：图片及内容基于https://www.bilibili.com/video/av95949609

BF算法

原理分析

Brute Force 暴力算法

用来在主串中查找模式串是否存以及出现位置

核心就是回溯

如果模式串下标 j 始终没有到达'\0'则没有找到

如果主串下标 i 最后到达了'\0'则没有找到

复杂度分析

完整代码

#include<iostream>
using namespace std;
int BF(char S[], char T[]) {
    int i = 0, j = 0,start=0;
    while (S[i]!='\0'&&T[j]!='\0') {
        if (S[i] == T[j]) {         //相等的话，i，j都后移一位
            i++; j++;
        }
        else {                        //一旦有不相等的，回溯。i回到起始位置加一，j回到模式串头
            start++;
            i = i - j + 1;
            j = 0;
        }
    }
    if (T[j] == '\0') return start; //也可以return i-j;
    //if (S[i] == '\0') return -1;  //主串到达'\0'说明没找到
    else return -1;                  //模式串没到达'\0'说明没找到
}
int main() {
    char S[] = "DABCDABD";
    char T[] = "ABD";
    int i=BF(S, T);
    if (i>=0) {
        cout << "已找到，在主串下标为"<<i<<"的地方"<<endl;
    }
    else cout << "未找到" << endl;
    return 0;
}

 KMP算法

原理分析

比BF算法高效，区别是主串的下标 i 不会回溯，一直前进。而模式串下标 j 回溯到特定位置。

关键是模式串找最大的相同的前后缀，用next数组记录前后缀字符数。

对模式串回溯的正确性分析：如上图已经找到模式串中最大长度的相等的前后缀且模式串前后缀以及中间的元素已经与主串匹配。

模式串中ab!=cd,故模式串中ab!=主串中cd,模式串中的前缀ab没有再与主串比较的必要，故模式串下标 j 移动到c，主串下标 i 不动

next数组

完整代码

#include<iostream>
using namespace std;
void getNext(char *T, int *next) {
    int j = -1;   //前缀
    int i = 0;    //后缀
    next[0] = -1;
    while (i < strlen(T)) {
        if (j == -1 || T[i] == T[j] ){
            i++; j++;
            next[i] = j;
        }
        else {
            j=next[j];  //回溯
        }
    }
}
int KMP(char S[], char T[],int *next) {
    int i = 0, j = 0;
    int lengthS = strlen(S);
    int lengthT = strlen(T);
    while (i < lengthS && j < lengthT) {
        if (j== -1||S[i] == T[j]) {
            i++; j++;
        }
        else {
            j = next[j];
        }
    }
    if (j == lengthT) return (i - j);
    else return -1;
}

int main() {
    char S[] = "DABCDABD";
    char T[] = "ABC";
    int next[100];
    getNext(T,next);
    int i = KMP(S, T,next);
    if (i>=0) {
        cout << "已找到，在母串下标为"<<i<<"的地方"<<endl;
    }
    else cout << "未找到" << endl;

    return 0;
}

BF算法和KMP算法比较

在KMP算法中 j == -1因为next数组next[0]= -1，得到 j 可能为-1