KMP字符串

思路分析

暴力做法

我们很容易可以想出来，对于模式串s中的每一个字符进行情况枚举，与模板串p进行匹配
不过很明显，这样做效率是极其低下的，因为它是暴力枚举，没有利用任何已知信息

若模式串s的长度是$n$，模板串p长度是$m$，它的时间复杂度是$O(mn)$的

那么我们可以考虑利用某些已知的信息，来减少枚举数量，这就是我们KMP算法的思路了

KMP算法

这里推荐拿案例，自己手工模拟几遍，光听或者是看，确实有点难理解

两个字符串的下标都是从$1$开始，这样可以维护代码简洁与易懂

我们每次是拿$s[i]$ 与 $p[j + 1]$进行比较的，若不等则执行$j = ne[j]$

已知信息：找出模式串$p$的从第$0$个字符开始到第i个字符结尾的子串中，前缀与后缀最大相同的位数$len$

这时候若模板串p的某一个子串长度是$m$, $p[0]$到$p[len]$和$p[m - len + 1]$到$p[m]$完全一样的

前缀就是从前往后数的字符串，后缀就是从后往前走，

所以当在这个子串的末位匹配时，当$m + 1$匹配失败时候，我们可以不用从第一个字符开始匹配，我们可以直接从第$len$的地方开始匹配，这个$len$就是我们需要知道的元素

模板串P:1231234,4与模式串匹配不对了，但是前面123123是匹配了的，我们下一次匹配之前从第第四个数组也就是1来比较就行了，因为123已结是匹配了的
模式串：-1231235
模板串：-1231234， 4和5不匹配，下一次从1开始
下一次：------1231234，依次类推

上面字符串是对齐了的，看过视频后大概就可以理解这个（确实描述的不太好）

再举一个例子，$eg:$ 字符串，abababa

KMP算法核心步骤是求ne[]，和匹配

$next$[ ]在c++某些库被占用，用$ne$[ ]稳一点

当然求$ne$[ ]数组也可以看做是自己与自己匹配的一个过程，只是后面的具体逻辑不太一样

求ne[ ]的过程

for (int i = 2, j = 0; i <= n; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j]; 
    // 因为我们是从前往后找每一个i 的ne值，因此用到的一定是已经求出来的
    //模板串短的话，可以考虑暴力做法。KMP算法自己手工模拟几遍效果比较好
    if (p[i] == p[j + 1]) j ++ ; //如果下一个匹配成功，那么ne[ ]的下标也可以右移
    ne[i] = j;
}

和模式串s匹配过程

for (int i = 1, j = 0; i <= m; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j]; 
    //当前字符未匹配成功，并且不是第一个字符时， j = ne[j]，前后缀是相等的，利用了已有信息
    if (s[i] == p[j + 1]) j ++ ;
    //结束条件有两个，如果这时候第i个字符匹配上了，那么 j ++ 
    if (j == n)
    {
        //一组匹配成功的具体逻辑

        //j = ne[j];这一步是进行下一次匹配
    }
}

代码

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;  //从下标1开始读入字符串

    for (int i = 2, j = 0; i <= n; i ++ ) //求ne[ ]数组
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ ) // p 与 s的匹配过程
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            //匹配成功，输出匹配成功的首下标，本来应该是i - n + 1，不过我们是按下标1开始算的，最后要减1
            j = ne[j];
            //利用已有信息进行下一次匹配
        }
    }

    return 0;
}