KMP算法 模式匹配

#include <stdio.h>

#include <string.h>

void get_next (char *shorts , int *next)

{

    // 试着推演，见照片的头一个表

    // 图片链接：https://fishc.com.cn/thread-146096-1-1.html

    int i = 1 ;

    int j = 0 ;

    next[1] = 0 ;

    while (i<strlen(shorts))

    {

        if (0==j || shorts[i-1] == shorts[j-1])

        // 当j为0时，意味着单个字符的遍历对比结束

        {

            i++ ;

            j++ ;

            next[i]=j ; // next数组写入

        }

        else

        {

            j = next[j] ; // 回溯过程，这是KMP算法里的精髓

        }

    }

}

int KMP (char *longs , char *shorts) // 传入的是指针类型

{

    int i = 1 ;

    int j = 1 ;

    int next[100] ; // 尽可能大一点

    get_next(shorts,next); // 获得next数组

    // KMP算法中，起关键作用的是搜索串的"架构"，与原串无关

    // 比BF暴风算法有效的是，我们会大大减少重复并且是无意义的检查

    // KMP算法能确保每一次的检查都是必要的，而这全依赖于next数组

    while (i<=strlen(longs) && j<=strlen(shorts))

    {

    // 试着推演，见照片的下一个表

        if (0==j || longs[i-1] == shorts[j-1])

        {

            i++ ;

            j++ ;

        }

        else

        {

            j = next[j] ;

        }

    }

    if (j > strlen(shorts))

    {

        return i-j; // 记住我们会把原串的第一位下标为0

    }

    else

    {

        return -1 ; // -1 表示没匹配到

    }

}

int main ()

{

    int pos = KMP("xcababbabce","abbab"); // 传入原串，搜索串

    printf("%d\n",pos);

    return 0 ;

}