KMP算法

一、何谓模式串匹配

模式串匹配，就是给定一个需要处理的文本串（理论上应该很长）和一个需要在文本串中搜索的模式串（理论上长度应该远小于文本串），查询在该文本串中，给出的模式串的出现有无、次数、位置等。

模式串匹配的意义在于，如果我是一个平台的管理员，我可以针对一篇文章或者一句话，搜索其中某个特定脏字或者不雅词汇的出现次数、位置——次数可以帮助我决定采取何种等级对于该用户的惩罚方式，而位置则可以帮助我给每一个脏词打上“*”的标记来自动屏蔽这些脏词。

二、浅析

哦呵呵这个算法的名字比较诡异是因为有三位伟大的科学家共同设计完成……分别是

~~然而我并不知道他们是谁~~

首先要理解，朴素的单模式串匹配大概就是枚举每一个文本串元素，然后从这一位开始不断向后比较，每次比较失败之后都要从头开始重新比对，大概期望时间复杂度在

而

比如我们考虑一组样例：

模式串：abcab
文本串：abcacababcab

首先，前四位按位匹配成功，遇到第五位不同，而这时，我们选择将

模式串：   abcab
文本串：abcacababcab

但有时不光只会有单个字符重复：

模式串：abcabc
文本串：abcabdababcabc

当我们发现在第六位失配时，我们可以将模式串的第一二位移动到第四五位，因为它们相同

模式串：   abcabc
文本串：abcabdababcabc

那么现在已经很明了了，

1、我们的失配数组应当建立在模式串意义下，而不是文本串意义下。因为显然模式串要更加灵活，在失配后换位时，更灵活简便地处理。

2、如何确定位置呢？

首先我们要明白，基于先决条件

在模式串

上述即为移位法则

3、从前缀后缀来解释

首先解释前后缀(因为太简单就不解释了

给定串：ABCABA
前缀：A,AB,ABC,ABCA,ABCAB,ABCABA
后缀：A,BA,ABA,CABA,BCABA,ABCABA

其实刚才的移位法则就是对于模式串的每个前缀而言，用

三、代码实现

1、

2、对于如何和文本串比对，很简单：

 int j;
    j=0;//j可以看做表示当前已经匹配完的模式串的最后一位的位置 
    //如果楼上看不懂，你也可以理解为j表示模式串匹配到第几位了 
    for(int i=1;i<=la;i++)
       {
          while(j&&b[j+1]!=a[i])j=kmp[j];
          //如果失配 ，那么就不断向回跳，直到可以继续匹配 
          if (b[j+1]==a[i]) j++;
          //如果匹配成功，那么对应的模式串位置++ 
          if (j==lb) 
          {
          cout<<i-lb+1<<endl;
          j=kmp[j];
          //继续匹配 
          }
       }

3、那么我们该如何处理

 j=0;
    for (int i=2;i<=lb;i++)
       {     
       while(j&&b[i]!=b[j+1])
       //此处判断j是否为0的原因在于，如果回跳到第一个字符就不 用再回跳了
       j=kmp[j];    
        //通过自己匹配自己来得出每一个点的kmp值 
       if(b[j+1]==b[i])j++;    
       kmp[i]=j;
        //i+1失配后应该如何跳 
       }

那么这个“自己匹配自己”该如何理解呢？我们可以这么想：首先，在单次循环只有一个

并且

贴标程：

#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la,lb,j; 
char a[MAXN],b[MAXN];
int main()
{
    cin>>a+1;
    cin>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for (int i=2;i<=lb;i++)
       {     
       while(j&&b[i]!=b[j+1])
        j=kmp[j];    
       if(b[j+1]==b[i])j++;    
        kmp[i]=j;
       }
    j=0;
    for(int i=1;i<=la;i++)
       {
          while(j>0&&b[j+1]!=a[i])
           j=kmp[j];
          if (b[j+1]==a[i]) 
           j++;
          if (j==lb) {cout<<i-lb+1<<endl;j=kmp[j];}
       }

    for (int i=1;i<=lb;i++)
    cout<<kmp[i]<<" ";
    return 0;
}

那么时间复杂度为

题外话：本来想扯摊还分析来着，但是

每次位置指针 $Theta(len_N + len_M) = Theta(N + M)Θ(lenN+lenM)=Θ(N+M) 的$

总之很迷就对了（逃

其实我们也可以发现，

参考文章：

　　　　　https://pks-loving.blog.luogu.org/zi-fu-chuan-xue-xi-bi-ji-qian-xi-kmp-xuan-xue-di-dan-mu-shi-chuan-pi-post（本文主体）

　　　　　https://blog.csdn.net/gao506440410/article/details/81812163

KMP算法

一、何谓模式串匹配

二、浅析 KMPKMP 之思想

三、代码实现

二、浅析