前言

KMP\text {KMP} 是我觉得比较难理解的算法之一。

具体可以去别的博客里去多了解一下,这里具体讲思路。

我看过的大多数博客都写的很学术,很长,既没有能力也没有耐心去看,所以这东西就被认为难学。

其实还是挺简单的吧。

所谓失配指针,就是指向在当前字符的前面的离他最近且和它相等的字符的坐标。

设要求字符串 a\text a 里有多少个子串等于字符串 b\text {b}

算法流程

  1. 我们先预处理失配指针,具体实现和理解下面会讲。

  2. 然后用 22 个指针 iijjiiaa 字符串, jjbb 字符串,j=( j\text j= (\ \text j 的失配指针 )) 直到 j=0j=0 的时候或者 b[j+1]b[j+1] 等于a[i+1]a[i+1]j++j++

  3. 如果 jj 等于 bb 的长度,就已经匹配了。

  4. 如果你需要没有重叠的字串, jj 归零,不然,就再等于 jj 的失配指针。

失配指针原理

用人话说,就是上面那句话:指向在当前字符的前面的离他最近且和它相等的字符的坐标。

再直观一点,画个图(画的有点丑,要怪就怪学校的鼠标不好用吧)

理解后,就先来说 KMP\text {KMP} 匹配的部分吧,上面已经说了具体的步骤,这里给一下代码:

int kmp(){
    int j=0;
    for(int i=0;i<lenb;++i){
        while(j>0&&b[i+1]!=a[j+1]) j=p[j];
        if(b[i+1]==a[j+1]) j++;//上面和这行对应第二步,这里懒得加注释了。
        
        if(j==lena){
            ans++;//这个随意
            //cout<<i+2-lena<<endl;
            j=p[j];//这里看具体题目,现在是允许有重叠部分的字串,如果不允许j要变成0
        }
        
    }
}

现在再来说说预处理失配指针的思路。

其实和 KMP\text {KMP} 的代码差不多,是自己匹配自己。

流程

  1. 22 个指针 iijjj=( j\text j= (\ \text j 的失配指针 )) 直到 j=0j=0 的时候或者 b[j+1]b[j+1] 等于b[i+1]b[i+1]j++j++
  2. b[i]b[i] 的失配指针指向的就是 jj
代码:
void pre(){
    p[1]=0;
    int j=0;
    for(int i=1;i<lena;++i){
        while(j>0&&a[j+1]!=a[i+1]) j=p[j];
        if(a[j+1]==a[i+1]) j++;
        p[i+1]=j;
    }
}