KMP匹配算法 C语言版本

这个就是用于找到子串在母串中出现的位置，然后相较于传统的比对，进行了回溯的优化，使算法运行效率更高。这个学过数据结构的同学应该知道，在此不过多阐述。
这个算法目前是只能计算出第一次出现的位置，我是用作解析Json数据的。一共就两个函数，一个是get_next数组的 就是回溯指标，具体的原理可以去看看书或者找视频。然后就是找到位置IndexOf，返回位置 0表示没有找到 1表示第一个位置对应数组的下标0 。

#include 

typedef unsigned char UINT8;
typedef signed char INT8;
typedef unsigned short UINT16;
typedef signed short INT16;
typedef unsigned int UINT32;
typedef signed int INT32;
typedef long long UINT64;

void get_next(UINT8 *data, UINT8 *next, UINT8 DataLen);
UINT8 IndexOf(UINT8 *Data, UINT8 *Buf,UINT8 DataLen,UINT8 BufLen);

UINT8 IndexOf(UINT8 *Data, UINT8 *Buf,UINT8 DataLen,UINT8 BufLen)
{
    UINT8 i=0, j=0;
    UINT8 next[255];

    get_next(Buf,next,BufLen);
    while ((i
        if((j==0)||(Data[i]==Buf[j]))
        {
            i++; 
            j++;
        }
        else
        j=next[j];
    }

    if(j>=BufLen)
        return i-BufLen;
    else
        return 0;
}


void get_next(UINT8 *data, UINT8 *next, UINT8 DataLen)
{
    int i, j;
    i = 1;
    j = 0;
    next[1] = 0;
    while (i < DataLen - 1)
    {
        if (j == 0 || data[i] == data[j]) // data[i]表示后缀的单个字符，data[j]表示前缀的单个字符
        {
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j]; //若字符不相同，则j值回溯
    }
}


int main(int argc, char const *argv[])
{
    UINT8 data[]="#goodgoogle";
    UINT8 Buf[]="#google";
    printf("index=%dn",IndexOf(data,Buf,sizeof(data),sizeof(Buf)));
    return 0;
}

结果是

index=4

第一次写文章有借鉴其他人的，感谢链接: link