KMP

KMP

描述：

​ 子串的匹配算法。

核心：

KMP算法分为两个部分： 求next数组 和匹配字符串

（1）求next数组：
（1.1）先让子串最近一个与其相同的位置，然后继续判断，直至能匹配上或者回到第一个字符位置。
（1.2）回到能匹配到的地方后，继续开始匹配，匹配成功，则j向后移，
（1.3）记录当前子串字符i的能匹配上的位置
（1.4）遍历整个子串，便能找出子串中能匹配上的位置
（2）匹配字符串：利用子串的next数组进行匹配，优化，不用每次匹配失败都回到子串的第一个字符
（2.1）匹配不成功，每次匹配前，先让子串回到能与主串匹配的位置
（2.2）然后进行匹配，如果匹配成功，就把子串匹配的位置向后移
（2.3）如果子串j匹配完了，即j == n时，说明在主串中找到了子串匹配串，则进行输出该位置，并且将j回到能匹配的位置
（2.4）逐一匹配主串中所有字符即可

代码模板：

//求next数组
    for(int i = 2, j = 0; i <= n; i ++ ) //第一位肯定是0，直接从第二位开始计算
    {
        while(j && p[i] != p[j + 1])j = ne[j];        //当j退到0或者，主串和子串的值对不上的时候，让j回到能对上的位置，直到找到或者无路可退为止
        if(p[i] == p[j + 1])j ++;                     //if能对上就让子串继续往后对
        ne[i] = j;                                    //记录下该点时的next数组值
    }

//开始匹配
    for(int i = 1, j = 0; i <= m; i ++)
    {
        while(j && s[i] != p[j + 1])j = ne[j];        //当j退到0或者，主串和子串的值对不上的时候，让j回到能对上的位置，直到找到或者无路可退为止
        if(s[i] == p[j + 1])j ++;                     //if能对上就让子串继续往后对
        if(j == n)
        {
            printf("%d ", i - n);                     //输出此时的起始下标（该位置减去子串总长度，即子串起始下标）
            j = ne[j];                                //将子串恢复到他下次能够匹配的位置
        }
    }