bf算法和kmp算法代码

BF算法和KMP算法都是字符串匹配算法，用于在一个主串中查找一个子串是否存在。BF算法的思想是暴力匹配，即从主串的第一个字符开始，依次和子串的每一个字符进行比较，如果匹配失败，则主串和子串都需要回溯，直到找到匹配的子串或者主串遍历完毕。KMP算法则是通过预处理子串的信息，来避免在匹配过程中的回溯，从而提高匹配效率。

下面是BF算法和KMP算法的代码：

BF算法：

bool BF(char a[],char b[]){
    int index1 = 0;//指向a的头部
    int index2 = 0;//指向b的头部
    for(int i = 0;i<strlen(a);i++){//轮数
        if(a[index1]==b[index2]){
            index1++;
            index2++;
        }else{
            index1 = i+1;
            index2 = 0;
        }
        if(index2==strlen(b))
            return true;
    }
    return false;
}

int main(){
    char a[6] = {'a','c','a','b','d','a'};
    char b[3] = {'a','b','d'};
    char c[3] = {'a','b','e'};
    if(BF(a,b))
        printf("匹配\n");
    else
        printf("不匹配\n");
    if(BF(a,c))
        printf("匹配\n");
    else
        printf("不匹配\n");
    return 0;
}

KMP算法：

void getNext(char* p, int* next) {
    int pLen = strlen(p);
    int k = -1;
    int j = 0;
    next[0] = -1;
    while (j < pLen - 1) {
        if (k == -1 || p[j] == p[k]) {
            ++k;
            ++j;
            next[j] = k;
        }
        else {
            k = next[k];
        }
    }
}

bool KMP(char* s, char* p) {
    int sLen = strlen(s);
    int pLen = strlen(p);
    int i = 0;
    int j = 0;
    int next[pLen];
    getNext(p, next);
    while (i < sLen && j < pLen) {
        if (j == -1 || s[i] == p[j]) {
            ++i;
            ++j;
        }
        else {
            j = next[j];
        }
    }
    if (j == pLen) {
        return true;
    }
    else {
        return false;
    }
}

int main() {
    char s[] = "ababcabcacbab";
    char p[] = "abcac";
    if (KMP(s, p)) {
        printf("匹配\n");
    }
    else {
        printf("不匹配\n");
    }
    return 0;
}