KMP算法--C语言实现

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

void GetNext(char* sub, int next[])
{
    int lenSub = strlen(sub);
    next[0] = -1; // 初始第一个为 -1 第二个为 0
    next[1] = 0;
    int i = 2;
    int k = 0;

    while (i < lenSub)
    {
        if(k == -1 || sub[i-1] == sub[k])
        {
            next[i] = k+1;
            i++;
            k++;
        }
        else
        {
            k = next[k];

        }


    }

}

// 然后是使用next数组进行KMP字符串匹配的核心函数
int KMP(char* str, char* sub, int pos)
{
    assert(str != NULL && sub != NULL);
    int lenStr = strlen(str);
    int lenSub = strlen(sub);
    if(lenStr == 0 || lenSub == 0) return -1;
    if(pos < 0 || pos >= lenStr) return -1;

    int *next = (int*)malloc(sizeof(int) * lenSub);
    assert(next != NULL);

    GetNext(sub, next);
    int i = pos;
    int j = 0;

    while (i < lenStr && j < lenSub)
    {
        if(j == -1 ||str[i] == sub[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];

        }
    }
    if(j >= lenSub)
    {
        return i - j;
    }
    return -1;

}



int main() {



    printf("%d\n", KMP("abababnabcabdce", "abcd", 0));
    printf("%d\n", KMP("abababnabcabdce", "ab", 0));
    printf("%d\n", KMP("abababnabcabdce", "e", 0));

    return 0;
}

运行结果：