/*
* 主题：KMP模式匹配算法
* 作者：熊猫大大
* 时间：2020-09-22
*/
#include <stdio.h>
// 获取子串的next数组
void getNext(char *pattern,int next[]) 
{
    //初始化变量
    int i, j, len;
    len = strlen(pattern);
    i = 0;
    j = -1;
    next[0] = -1;//固定值
    // 循环设置next数组每个位置的值
    while (i < len) 
    {
        if (j == -1 || pattern[i] == pattern[j]) 
        {
            i++;
            j++;
            next[i] = j;
        }
        else 
        {
            j = next[j];
        }
    }
}
// kmp模式匹配 -1表示匹配失败，其他值表示匹配位置
int kmpIndex(char *main,char* pattern,int next[]) 
{
    // 初始化变量
    int i, j, mainLen, patternLen;
    i = 0;
    j = -1;
    mainLen = strlen(main);
    patternLen = strlen(pattern);
    // 查找匹配串的位置
    while (i < mainLen&&j < patternLen) 
    {
        // 通过next快速调整j的位置
        if (j == -1 || main[i] == pattern[j]) 
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j >= patternLen) //匹配成功
    {
        return i - patternLen;
    }
    else //失败
    {
        return -1;
    }
}

int main()
{
    char * pattern = "bcd";
    int* next= (int*)malloc(sizeof(int)*strlen(pattern));
    getNext(pattern,next);
    char * main = "abcd";
    printf("位置：%d", kmpIndex(main, pattern, next));
}