bf和kmp算法的c语言实现

以下是BF算法和KMP算法的C语言实现：

BF算法：

#include <stdio.h>
#include <string.h>

int IndexBF(const char* S, const char* T) {
    if (S == NULL || T == NULL) // 判断是否为空指针
        return -1;
    int i = 0; // 主串指针
    int j = 0; // 模式串指针
    int slen = strlen(S);
    int tlen = strlen(T);
    while (i < slen && j < tlen) {
        if (S[i] == T[j]) {
            ++i;
            ++j;
        } else {      // 回溯
            i = i - j + 1; // i = i - (j - 1) = i - j + 1
            j = 0;
        }
    }
    if (j == tlen)
        return i - j; // 匹配成功
    else
        return -1; // 匹配失败
}

int main() {
    char S[] = "hello world";
    char T[] = "world";
    int index = IndexBF(S, T);
    printf("%d\n", index); // 输出：6
    return 0;
}

KMP算法：

#include <stdio.h>
#include <string.h>

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

int IndexKMP(const char* S, const char* T, int* next) {
    if (S == NULL || T == NULL || next == NULL)
        return -1;
    int i = 0, j = 0;
    int slen = strlen(S);
    int tlen = strlen(T);
    while (i < slen && j < tlen) {
        if (j == -1 || S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j == tlen)
        return i - j;
    else
        return -1;
}

int main() {
    char S[] = "hello world";
    char T[] = "world";
    int next[strlen(T)];
    getNext(T, next);
    int index = IndexKMP(S, T, next);
    printf("%d\n", index); // 输出：6
    return 0;
}