为方便 i，j 更清晰的移位，字符数组第一位丢掉不要，即序号从1开始

引子 – BF算法

主串S和模式串P匹配过程途中失败，则模式串指针 j = 1 (从头开始)，主串指针需要回溯到 i = (i – j + 1) + 1 (本次匹配的初始位置 i0 + 1)。最坏的时间复杂度即为 (n – m) * m + m = (n – m + 1) * m = O(nm)

阿Q对KMP算法的理解

BF算法，每次都把 i 回溯，j 退为1（正常人都能想到）。但是在匹配过程中主串还需要要回溯嘛？如果回溯，之前匹配的信息是否没利用上了？

KMP算法好处就在于主串的指针是只增不减的，其当次匹配失败的位置的前K个字符（倒过来）如果和模式串的前K个字符是相同的，那本次匹配成功的就有K个字符，如下图：

由图可以看出下一次匹配启动时：主串的指针 i 不变，模式串逻辑上往后移动了 j – k （注意是逻辑上）。

那么关键在于哪呢？阿Q：在于模式串当前位置匹配失败后，下一次 j 应该去哪。【 next[j] ♥】

next[j]

注意：以下讨论的序号都是从 1 开始，若从零开始， next[j] = next[j] – 1

下面我们来个next[j]的题目，看图就理解了（做题人视角）

如果编写成程序呢？该怎么办？不可能说比 {aba}的前缀和后缀的交集吧（不服可以试试）

那接下来我们换种思路来考虑这个问题。（编程视角）

nextval(x)

编程任务（408统考不考KMP算法题）

阿Q备注：以下均用定长顺序存储实现 – SString（参考:串的存储）

1、编写 KMP算法（获取模式串 next[j] 和 nextval[j]）

// C实现
// 假设先通过代码实现了next[j]的计算
// 数组下标从1开始，0不管
int Index_KMP(SString S, SString P, int next[]){
    int i = 1, j = 1;
    while(i <= S.length && j <= P.length) // 不超过上限
    {
        if(S.ch[i] == P.ch[j] || j == 0) ++i, ++j;  // 阿Q备注：此时 j = 0 时，i也需要 + 1
        else j = next[j];
    }
    // P找完了
    if(j > P.length) return i - P.length;
    else return 0;
}

// 下面才是重头戏，编程实现next[j]的计算
void get_next(SString P, int next[]){
    next[1] = 0; // 规定
    int i = 1, j = 0;
    // 给 next 各项赋值
    while(i < P.length)
    {
        /*
            已知 next[j] 求 next[j + 1]
                p.ch[next[j]] == p.ch[j] -> next[j + 1] = next[j] + 1
                p.ch[next[j]] != p.ch[j] -> j = next[j] (递归) -> p.ch[k*] == p.ch[j]
                j == 0 -> next[j+1] = next[1] + 1;
        */
        if(j == 0 || P.ch[i] == P.ch[j]){
            ++i, ++j;
            next[i] = j; //阿Q备注： j在此处为 k* + 1，在循环外始终为 k*
            // 阿Q思考：经测试：next[i] = next[j] + 1 出错，问题在哪呢？ 还是 j = k* + 1，不为 i -1
            // 经测速 next[i] = next[i - 1] + 1 也出错，问题在哪呢？ 因为i只增，next[2] = next[1] + 1 = 2 错误
        }
        else j = next[j];
    }
}

// next的改进算法
void get_nextval(SString P, int nextval[]){
    int i = 1, j = 0;
    nextval[1] = 0; // nextval[1] = next[1]
    /*
        与next[j]不同点在于：
            还需进一步判断 p.ch[next[j]] ?= p.ch[next[next[j]]]
    */
    while(i < P.length){
        if(j == 0 || P.ch[i] == P.ch[j]){
            ++i, ++j;
            // 下面为不同点，需额外判断
            if(P.ch[i] == P.ch[j]) nextval[i] = nextval[j];
            else nextval[i] = j;
        }
        else j = nextval[j];
    }
}

// 经测试，代码正确

2、模式串在主串中有多少个完全匹配的字串

// C实现
int count_total_index_KMP(SString S, SString P, int next[], int index[])
{
    int i = 1, j = 1;
    int count = 0; // 记录完全匹配的个数
    // 下标从 1 ~ length
    while (i <= S.length){
        while(j <= P.length && i <= S.length){
            if(S.ch[i] == P.ch[j] | j == 0) ++i,++j;
            else j = next[j];
        }
        if(j > P.length){
            count += 1;
            // j 回溯到 1（从头比）, i = i - P.length + 1
            index[count] = i - P.length;
            j = 1; 
            i = i - P.length + 1;
        }
    }
    return count;
}
// 阿Q：上述函数是重点，以下为测试
int main(){
    // 创建主串S和模式串P
    SString S, P;
    char *chs = "zaabaabbabaabaabbabaab"; // 第一位随意插值，下标从1开始
    int slen = 21;
    int i = 1;
    for(;i <= slen;i++) S.ch[i] = chs[i];
    S.length = slen;
    char *chp = "zabaa";
    int plen = 4;
    for(i = 1; i <= plen; i++) P.ch[i] = chp[i];
    P.length = 4;
    int next[5];
    get_next(P,next);
    //P在S中完全匹配
    //分段匹配即可，定一个数组记录各次匹配成功的位置。
    //int index[MAXINDEXLEN];
    /*
        范围： 1->a1 ； a1 + 1->a2; ...; an-1 + 1 -> an; an + 1->MAXINDEXLEN
    */
    // 需要临时创建一个SString temp 存放主串中未匹配的剩余字符串
    // 每段匹配成功的pos + 当前匹配开头的位置 ak + 1
    // 阿Q：上述当然可以，但最后能修改下 Index_KMP函数（更简洁）
    // Index_KMP 函数 修改为 count_total_index_KMP 函数

    int index[MAXINDEXLEN];
    int count = count_total_index_KMP(S,P,next,index);
    printf("%d\n", count);
    for(int i = 1; i <= count; i++)
        printf("%d ",index[i]);
    return 0;
}

/*
输出：
4
2 8 11 17 
*/