c语言实现KMP算法

1.源码实现

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

void getnext(const char *temp, int *f)
{
    int n = strlen(temp);
    int i, j;

    f[0] = f[1] = 0;

    for(i=1; i<n; i++)
    {
        j = f[i];

        while(j && temp[i] != temp[j])
        {
            j = f[j];
        }

        f[i+1] = temp[i] == temp[j] ? j + 1 : 0;
    }
}

void findstr(const char *str, const char *temp, int *f)
{
    int n = strlen(str);
    int m = strlen(temp);
    int i, j = 0;

    /*生成next数组*/
    getnext(temp, f);

    for(i=0; i<n; i++)
    {
        /*不停地转移, 直到可以匹配或者走到0*/
        while(j && str[i] != temp[j])
        {
            j = f[j];
        }

        /*如果相等, 模板串中待匹配位置可以移一位了*/
        if(str[i] == temp[j])
        {
            j++;
        }

        if(j == m)
        {
            printf("%d\n", i-m+1);
        }
    }
}

int main()
{
    char *a = "hello world";
    char *b = "llo";
    int c[100];

    memset(c, 0x00, sizeof(c));

    findstr(a, b, c);

    return 0;
}

2.编译程序

$ gcc -o example example.c

3.运行程序

$ ./example
2