#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <memory.h>

int BF_Search(const char* MainStr, const char* SubStr)
{
    //BF算法逻辑：
    //1.申请两个指针i和j，分别指向主串和子串的开始位置
    int i = 0;
    int j = 0;

    //"ABCD" strlen=4
    //2.进入while循环，循环的条件是i和j还合法(换句话说就是还没有越界)
    while (i < strlen(MainStr) && j < strlen(SubStr))
    {
        //3.比较i和j指向的字符，如果相同，则让i和j同步向后移动一个位置
        if (MainStr[i] == SubStr[j])
        {
            i++;
            j++;
        }
        //4.如果不相同，则让指向子串的j变量，回退到开始位置(0下标)
        else
        {
            i = i - j + 1;
            j = 0;
        }
            
    }
    //5.如果while循环进不出，则说明查找结束了，只需要对j来做判断，就可以知道是否查找成功(j走出自身范围则找到，相反j未走出自身范围则没找到)
    if (j < strlen(SubStr))
    {
        return -1;
    }
    return i - j;
}

//获取next数组
int* Get_Next(const char* SubStr)
{
    //kmp求next数组的详细步骤(已知推未知) :
    //1.申请一个next数组，长度和子串长度一致
    int* next = (int*)malloc(strlen(SubStr) * sizeof(int));
    if (NULL == next)
        exit(EXIT_FAILURE);

    //2.将next数组的前两个格子直接赋值 - 1和0
    next[0] = -1;
    next[1] = 0;

    //3.申请一个变量j指向当前最新的已知其next值的字符(初始化为1号下标)
    int j = 1;

    //4.再申请一个变量NEX，用来保存当前字符的失配时，向前可以看到的最
    // 长公共前后缀的共有长度(换句话说就是可以有多少个字符可以不用比较)
    int NEX = next[j];//0

    //5.进入while循环，循环条件是j合法(j最多指向倒数第二个字符)
    while (j+1 < strlen(SubStr))
    {
        //9.如果一直比较失败，也就是NEX == -1了，则此时将NEX + 1变成0
        // 赋值给下一个字符的next数组的位置
        
        //6.用当前j指向的字符和其NEX保存的回退位置的字符进行比较
        //7.如果相同，则让NEX + 1, 然后赋值给下一个字符的next数组位置
        // (相当于将原本此时的左绿和右绿线末尾又各自了一个相同的字符，
        // 所以左绿和右绿线共有长度 + 1)
        if (NEX==-1 || SubStr[j] == SubStr[NEX])
        {
            next[++j] = ++NEX;
        }
        //8.如果不相同，则让NEX去保存其回退位置字符的回退位置，接着比
        // 较，直到比较成功，或者NEX触底(触底就是NEXT == -1)
        else
        {
            NEX = next[NEX];
        }
            
    }
    //10.当while循环退出，则next数组全部赋值完毕
    return next;
}

int KMP_Search(const char* MainStr, const char* SubStr)
{
    //BF算法逻辑：
    //1.申请两个指针i和j，分别指向主串和子串的开始位置
    int i = 0;
    int j = 0;

    //1.5 提供子串对应的next数组
    int* next = Get_Next(SubStr);

    //"ABCD" strlen=4
    //2.进入while循环，循环的条件是i和j还合法(换句话说就是还没有越界)
    while (i < (int)strlen(MainStr) && j < (int)strlen(SubStr))
    {
        //3.比较i和j指向的字符，如果相同，则让i和j同步向后移动一个位置
        if (j == -1 || MainStr[i] == SubStr[j])
        {
            i++;
            j++;
        }
        //4.如果不相同，则让指向子串的j变量，回退到开始位置(0下标)
        else
        {
            //i打死不回退
            j = next[j];//j回退到一个合适的位置  
        }

    }
    //5.如果while循环进不出，则说明查找结束了，只需要对j来做判断，就可以知道是否查找成功(j走出自身范围则找到，相反j未走出自身范围则没找到)
    if (j < strlen(SubStr))
    {
        return -1;
    }

    return i - j;
}
//获取nextval数组
int* Get_Nextval(const char* SubStr)
{
    int* next = Get_Next(SubStr);
    int *nextval = (int*)malloc(strlen(SubStr) * sizeof(int));
    if (NULL == nextval)
        exit(EXIT_FAILURE);

    nextval[0] = -1;

    for (int j = 1; j < strlen(SubStr); j++)
    {
        if (SubStr[j] != SubStr[next[j]])
            nextval[j] = next[j];
        else
            nextval[j] = nextval[next[j]];
    }

    free(next);
    return nextval;
}
int KMP_Search2(const char* MainStr, const char* SubStr)
{
    //BF算法逻辑：
    //1.申请两个指针i和j，分别指向主串和子串的开始位置
    int i = 0;
    int j = 0;

    //1.5 提供子串对应的next数组
    int* nextval = Get_Nextval(SubStr);

    //"ABCD" strlen=4
    //2.进入while循环，循环的条件是i和j还合法(换句话说就是还没有越界)
    while (i < (int)strlen(MainStr) && j < (int)strlen(SubStr))
    {
        //3.比较i和j指向的字符，如果相同，则让i和j同步向后移动一个位置
        if (j == -1 || MainStr[i] == SubStr[j])
        {
            i++;
            j++;
        }
        //4.如果不相同，则让指向子串的j变量，回退到开始位置(0下标)
        else
        {
            //i打死不回退
            j = nextval[j];//j回退到一个合适的位置  
        }

    }
    //5.如果while循环进不出，则说明查找结束了，只需要对j来做判断，就可以知道是否查找成功(j走出自身范围则找到，相反j未走出自身范围则没找到)
    if (j < strlen(SubStr))
    {
        return -1;
    }

    return i - j;
}
int main()
{
    /*const char* MainStr = "ABABCABCDABCDE";
    const char* SubStr = "ABCD";*/
    /*const char* MainStr = "AAAAAAAAAAB";
    const char* SubStr = "AAAAAAAB";*/
    //int index = BF_Search(MainStr, SubStr);
    const char* MainStr = "ABCBAAABCDABCDE";
    const char* SubStr = "ABCD";
    //int index = KMP_Search(MainStr, SubStr);
    int index = KMP_Search2(MainStr, SubStr);
    if (index == -1)
    {
        printf("没找到\n");
    }
    else
    {
        printf("找到了，且在%d找到的\n", index);
    }

    return 0;
}