//KMP串的模式匹配算法

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int* get_next(char t[], int length)

{

    int i = , j = -;

    int* next = (int *)malloc(length * sizeof(int));

    next[] = -;

    while (i < length)

    {

        if (j == - || t[i] == t[j])

        {

            i++;

            j++;

            next[i] = j;

        }

        else

        {

            j = next[j];

        }

    }

    return next;

}

int  Index_KMP(char s[], char t[], int sl, int tl, int next[])

{

    int j, i;

    j = ;

    i = ;

    while (j < tl && i < sl)

    {

        if (j == - || s[i] == t[j])

        {

            i++;

            j++;

        }

        else

        {

            j = next[j];

        }

    }

    if (j == tl)

    {

        return i - tl;

    }

    else

    {

        return ;

    }

}

//计算next函数修正值的算法

int *get_nextval(char t[], int length)

{

    int i = , j = -;

    int* nextval = (int*)malloc(length*sizeof(int));

    nextval[] = -;

    while (i < length)

    {

        if (j == - || t[i]==t[j])

        {

            j++;

            i++;

            if (t[j]!=t[i])

            {

                nextval[i] = j;

            }

            else

            {

                nextval[i] = nextval[j]; //回溯到下标为nextval[j]但元素与下标为nextval[i]的元素不相同的位置

            }

        }

        else

        {

            j = nextval[j];

        }

    }

    return nextval;

}

int main()

{

    char s[] = "acabaabaabcacaabc";

    char t[] = "abaabcac";

    char t2[] = "abcdabd";

    int tl = strlen(t);

    int sl = strlen(s);

    /*int *next = get_next(t, tl);

    int c = Index_KMP(s, t, sl, tl, next); //返回开始正确匹配的下标（s的下标）

    printf("%d\n", c);*/

    int l = strlen(t2);

    int * nextval = get_nextval(t,tl);

    /*for(int i = 0; i<l;i++)

    {

        printf("%d ",nextval[i]);

    }*/

    int c = Index_KMP(s, t, sl, tl, nextval);

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

    printf("\n");

    return ;

}