kmp

:::info 参考博文：https://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html
视频：https://www.acwing.com/video/259/
例题：https://www.acwing.com/problem/content/833/ :::

BF算法（暴力）

思想

BF算法就是暴力解，双重循环，有字符不匹配就回溯（i=i-j+1）

代码

int BFMatch(char *s,char *p)
{
    int i,j;
    i=0;
    while(i<strlen(s))
    {
        j=0;
        while(s[i]==p[j]&&j<strlen(p))
        {
            i++;
            j++;
        }
        if(j==strlen(p))
            return i-strlen(p);
        i=i-j+1;                //指针i回溯
    }
    return -1;    
}

KMP O(n)

思想

KMP算法解决的主要是优化BF算法，BF算法中第五趟不匹配时，第六趟j可以直接从2开始，不需要从0开始，这种多余的匹配过程在kmp中取消了。kmp不再进行i=i-j+1的指针回溯过程，只需要每次考虑j指针即可

next数组思想

利用了最大的后缀等于前缀的思想
首先来了解一下什么是前缀，什么是后缀。
以abacab为例
前缀：a``ab``aba``abac``abaca
后缀：b``ab``cab``acab``bacab
可以看出前后缀都不包括本身，其中最大的后缀等于前缀的意思是最长的相等的前后缀，在这个例子中是ab

代码

#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;
    // 求解next数组
    // 因为j=0是空的，j=1是第一个数，ne[1]=0，所以j从2开始
    for (int j = 2, k = 0; j <= n; j ++ )
    {
        // 如果不匹配则一直往后退。退到退无可退（k!=0）
        while (k!=0 && p[j] != p[k + 1]) k = ne[k];
        if (p[j] == p[k + 1]) k ++ ;
        ne[j] = k;
    }
    // 匹配
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        // 如果不匹配则一直往后退。退到退无可退（j!=0）
        while (j!=0 && s[i] != p[j + 1]) j = ne[j];
        // 如果匹配成功则看下一个 
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            //因为匹配成功后，p[j + 1]相当于是空字符，一定不匹配s[]中的任何字符，所以可以更新一次j
            // 如果此处不更新也可以，因为p[j + 1]相当于是空字符，一定不匹配s[]中的任何字符，在下一次循环中会进行j=ne[j]操作
            // 为了减少循环次数可以更新一次j
            j = ne[j];
            // 匹配成功后的逻辑
            printf("%d ", i - n);
        }
    }
    return 0;
}