KMP算法是对模式匹配算法的改进版，这个算法主要依靠子串中每个字符对应的next[j]的值，从而减少子串回溯的距离，减少时间复杂度。

next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。

KMP 匹配算法(1)

//----KMP 模式匹配算法---
//1.通过计算返回子串T的next数组;
//注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
void get_next(String T,int *next){
    int i,j;
    j = 1;
    i = 0;
    next[1] = 0;
    //abcdex
    //遍历T模式串, 此时T[0]为模式串T的长度;
    //printf("length = %d\n",T[0]);
    while (j < T[0]) {
        //printf("i = %d j = %d\n",i,j);
        if(i ==0 || T[i] == T[j]){
            //T[i] 表示后缀的单个字符;
            //T[j] 表示前缀的单个字符;
            ++i;
            ++j;
            next[j] = i;
            //printf("next[%d]=%d\n",j,next[j]);
        }else
        {
            //如果字符不相同,则i值回溯;
            i = next[i];
        }
    }
}

int count = 0;
//KMP 匹配算法(1)
//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP(String S,String T,int pos){

    //i 是主串当前位置的下标准,j是模式串当前位置的下标准
    int i = pos;
    int j = 1;

    //定义一个空的next数组;
    int next[MAXSIZE];

    //对T串进行分析,得到next数组;
    get_next(T, next);
    count = 0;
    //注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
    //若i小于S长度并且j小于T的长度是循环继续;
    while (i <= S[0] && j <= T[0]) {

        //如果两字母相等则继续,并且j++,i++
        if(j == 0 || S[i] == T[j]){
            i++;
            j++;
        }else{
            //如果不匹配时,j回退到合适的位置,i值不变;
            j = next[j];
        }
    }
    if (j > T[0]) {
        return i-T[0];
    }else{
        return -1;
    }
}

KMP 匹配算法(2)

//KMP 匹配算法(2)
//求模式串T的next函数值修正值并存入nextval数组中;
void get_nextVal(String T,int *nextVal){
    int i,j;
    j = 1;
    i = 0;
    nextVal[1] = 0;
    while (j < T[0]) {
        if (i == 0 || T[i] == T[j]) {
            ++j;
            ++i;
            //如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
            if(T[i] != T[j])
                nextVal[j] = i;
            else
            //如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置
                nextVal[j] = nextVal[i];
        }else{
            i = nextVal[i];
        }
    }
}

//KMP 匹配算法(2)
//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP2(String S,String T,int pos){

    //i 是主串当前位置的下标准,j是模式串当前位置的下标准
    int i = pos;
    int j = 1;

    //定义一个空的next数组;
    int next[MAXSIZE];

    //对T串进行分析,得到next数组;
    get_nextVal(T, next);
    count = 0;
    //注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
    //若i小于S长度并且j小于T的长度是循环继续;
    while (i <= S[0] && j <= T[0]) {

        //如果两字母相等则继续,并且j++,i++
        if(j == 0 || S[i] == T[j]){
            i++;
            j++;
        }else{
            //如果不匹配时,j回退到合适的位置,i值不变;
            j = next[j];
        }
    }

    if (j > T[0]) {
        return i-T[0];
    }else{
        return -1;
    }
}

彩蛋

//模式匹配,kmp算法,复杂度O(m+n)
//返回匹配位置,-1表示匹配失败,传入匹配串和模式串和长度
//可更改元素类型,更换匹配函数
#define MAXN 10000
#define _match(a,b) ((a)==(b))
typedef char elem_t;

int pat_match(int ls,elem_t* str,int lp,elem_t* pat){
    int fail[MAXN]={-1},i=0,j;
    for (j=1;j<lp;j++){
        for (i=fail[j-1];i>=0&&!_match(pat[i+1],pat[j]);i=fail[i]);
        fail[j]=(_match(pat[i+1],pat[j])?i+1:-1);
    }
    for (i=j=0;i<ls&&j<lp;i++)
        if (_match(str[i],pat[j]))
            j++;
        else if (j)
            j=fail[j-1]+1,i--;
    return j==lp?(i-lp):-1;
}

fail数据其实就是改进的next数组