kmp思想及模板代码

参考博文：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

思想

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)
        {
    
            j = ne[j];
            // 匹配成功后的逻辑
            printf("%d ", i - n);
        }
    }

    return 0;
}