KMP

字符串匹配的朴素算法，我就不讲了，我们直接进入KMP算法

KMP算法的优化在哪里

正常的朴素算法n^2是枚举每一个字符串每一个点为起点，与模板进行比对，比对一次是O(m)的复杂度
所以总复杂度就是O(nm)，这样的复杂度显然不符合要求，但我们可以发现对于这样的例子:



我们在发现了第四位B和D不一样了以后我们不是单纯的将起点右移一位，此时 i=4,j=3,
将a[i]与a[j+1]比较发现不同,我们将j返回到模板中nxt[j] (nxt数组将在后文讲到),j于是变成1


我们再次比较a[i]与a[j+1]发现相同,再i++,继续判断,以此类推

那么nxt[j]是什么以及我们应该如何预处理出模板中nxt[j]
1. 首先，对于一个字符串,我们要了解两个概念：”前缀”和”后缀”。

“前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。
对于字符串:"bread"
前缀： b , br , bre, brea
后缀: read, ead, ad , d

2. 那么知道了什么是前缀后缀,我们再来求nxt数组,通俗解释是”前缀”和”后缀”的最长的共有元素的长度就是nxt中存的值
拿"ABCDABD"举例*

nxt[1]=0    "A"的前缀和后缀都为空集，共有元素的长度为0；

nxt[2]=0    "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

nxt[3]=0    "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

nxt[4]=0    "ABCD"的前缀为[A, AB, ABC]，
后缀为[BCD, CD, D]，共有元素的长度为0；

nxt[5]=1    "ABCDA"的前缀为[A, AB, ABC, ABCD]，
后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

nxt[6]=2    "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，
后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

nxt[7]=0    "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，
后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

3.那么我们应该如何o(m)的求出模板的nxt预处理呢
其实采用的思路和查询操作相似
初始状态如下


当j==0零的时候我们要进行特判，因为nxt[0]==0,它将永远出不了循环所以当a[j+1]==a[i]或者j==0时就不继续j=nxt[j]而是跳出循环
实现如下

inline void getn(char a[N])
{
    for(register int i=2,j=0;i<=m;i++)
    {
        while(j&&a[j+1]!=a[i]) j=nxt[j];
        if(a[j+1]==a[i]) j++;
            nxt[i]=j;
    }
}

而完成了这步操作以后搜索操作也和这个差不多

实现如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <ctime>
using namespace std;
const int N=1000100;
char s1[N],s2[N];
int n,m,nxt[N],cnt=0;
inline void getn(char a[N])
{
    for(register int i=2,j=0;i<=m;i++)
    {
        while(j&&a[j+1]!=a[i]) j=nxt[j];
        if(a[j+1]==a[i]) j++;
        nxt[i]=j;
    }
}
inline void search(char a[N],char b[N])
{
    for(register int i=1,j=0;i<=n;i++)
    {
        while(j&&b[j+1]!=a[i]) j=nxt[j];
        if(b[j+1]==a[i]) j++;
        if(j==m) printf("%d
",i-m+1);
    }
}
int main()
{
    scanf("%s%s",s1+1,s2+1);
    n=strlen(s1+1),m=strlen(s2+1);
    getn(s2);search(s1,s2);
    for(register int i=1;i<=m;i++)
        printf("%d ",nxt[i]);
    return 0;
}