KMP

3.KMP

KMP算法主要用在字符串匹配上。

比如我们从字符串”acfacfgded”（需要在哪里找的字符串称为“文本串”）找其中是否包含字符串”acfg”（需要从文本串里找的字符串我们叫做“模式串”），我们一般会想到的解法是暴力求解，两层for循环，依次对模式串的每一个元素进行匹配，如果匹配失败，下次还从模式串的第一个进行匹配，这就导致了较高的时间复杂度（O(n×m)）。

而KMP算法不同之处就在于，当模式串的某个元素匹配失败后，不需要再从模式串的第一个元素从头开始匹配了，而是根据前缀表(next)找到模式串中一个最优的位置继续进行匹配

1.前缀表（next数组）：next[i] 记录的是模式串下标 i（包括i）之前的字符串的最长相等前后缀的长度。规定next[0]=0，因为第二个字符就不匹配，自然就回到第一个字符开始匹配

对于字符串”acdac”

另一种理解：将一个字符串固定不动，另外一个完全一样的字符串不断向右平移，直到两个字符串的交叉部分的元素相等，相等前后缀就是两个字符串的交叉部分

• 关于next数组的代码求解，思想类似kmp匹配两个字符串，特殊的只是将自己同时当作文本串和模式串进行匹配

2.得到前缀表后，设指向文本串的指针为i，指向模式串的指针为j，初始都为0；文本串数组为s[]，模式串数组为p[]，next数组为ne[]。文本串 “aabaabaafa”，模式串 “aabaaf” 。

• 开始循环比较s[i]与p[j]，当出现j>0且s[i]!=p[j]时

• 利用前缀表，让模式串向右平移一段位置（而不是像暴力那样直接模式串后移一位重新开始比较），找到文本串和模式串匹配的前后缀，就是改变指针j的位置，令j=ne[j-1](j>0)，即让当前指针值等于前一个字符对应的前缀值，不用再从头开始匹配。这里就让j=ne[4]=2，即指向b

AcWing 831.KMP字符串匹配

#include <iostream>
using namespace std;
const int N=1e6+10;
char s[N],p[N];//文本串和模式串
int n,m;
int ne[N];//next数组
 
int mian(){
    cin>>n>>p>>m>>s;
    
    //得到next数组
    for(int i=1,j=0;i<n;i++){//i从1开始，因为ne[0]=0
        while(j>0 && p[i]!=p[j]) j=ne[j-1];//要保证j>0 出现不匹配
        if(p[i]==p[j]) j++;//匹配 则后移继续
        ne[i]=j;//j就是代表已经匹配部分的长度
    }
    
    //进行kmp匹配
    for(int i=0,j=0;i<m;i++){
        while(j>0 && s[i]!=p[j]) j=ne[j-1];//要保证j>0 出现不匹配
        if(s[i]==p[j]) j++;//匹配 则后移继续
        if(j==n){//匹配结束
            printf("%d",i-n+1);
        }
    }
}