深化对KMP算法的理解

喜欢ヅ旅行 2022-12-15 12:48 5阅读 0赞

## KMP算法 ##

> 看到这么一句话：你的名字是我告白语中的子串

### 文章目录 ###

*   *  KMP算法
     *   *  参考代码
         *  预处理模式串的理解
         *  入门题目

**KMP一开始理解起来是比较困难的，下方是结合自己的理解写出来代码，仅作参考**，

（网上大部分人处理next数组时，对next数组整体移动了一格。但是我觉得不是特别好理解，所以我写的代码next数组并没有作移动）部分解释请参考注释。

### 参考代码 ###

#include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int N = 1e5+5;
    int next[N];
    void getNext(const char *s,int *next)
    {
        
        /*
        * description:
        *   构建模式串的前后缀相等的最大长度
        *   next[i]:存储串s[0...i]前后缀相等的最大长度
        *   特别考虑s[i] != s[j]:
        *   现在前后缀不相等，i不移动(除非j回退到0)，
        *   j需要回退，即缩小前后缀，但是要缩的尽可能小，
        *   由特殊的“对称性”，j应该回退到 next[j-1]
        * return: 
        */
        int len = strlen(s);
        int i = 1,j = 0;
        next[0] = 0;
        while(i < len)
        {
        
            if(s[i] == s[j])
            {
        
                next[i++] = ++j;
            }
            else
            {
        
               j > 0 ? j=next[j-1] : next[i++]=0;
            }
        }
    }
    int KMP(const char *t,const char *s)
    {
        
        /*
        * description: t串中找子串s
        * return: 匹配的第一个子串的首位置（index）
        */
        int i,j;
        i = j = 0;
        int lent = strlen(t);
        int lens = strlen(s);
        while(i < lent)
        {
        
            if(t[i] == s[j])
            {
        
                ++i;
                ++j;
            }
            else
            {
        
                j > 0 ? j=next[j-1] : i++;
            }
            if(j == lens) //如需匹配多个,虚拟模式串s[j]有元素（此时肯定失配）：j = next[j-1]
                break;
        }
         return j == lens ? (i-lens): -1;
    }
    int main()
    {
        
        const char *t = "aabcaabaabaaad";
        const char *s = "aabaabaaa";
        getNext(s,next);
        int first_pos = KMP(t,s);
        cout<<first_pos<<endl;
        return 0;
    }

### 预处理模式串的理解 ###

用两个“指针”：i, j （**i在后，j在前**）  
next\[i\]:存储串s\[0…i\]前后缀相等的最大长度，

*  前缀：去掉最后一个字符，以第一个字符开始的字符串；
 *  后缀，去掉第一个字符，以最后一个字符结尾的字符串；  
    比如：application,s\[0…4\]前缀：a,ap,app,appl,后缀：ppli,pli,li,i

初始化：`next[0] = 0, i = 1,j = 0`  
考虑的两种情况：

*  s\[i\] == s\[j\]: 两个指针均移动（`i++，j++`）
 *  s\[i\] != s\[j\]: j需要回退尽可能少，**j回退到next\[j-1\],  
    需要防止j-1数组越界，当j==0时，即此时j已经无法回退了，只有移动i才可能产生匹配的前后缀**。  
    (这里堪称KMP算法最难理解的地方)理解不了可以看下图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70_pic_center]

### 入门题目 ###

洛谷：[P3375 【模板】KMP字符串匹][P3375 _KMP]  
AC代码：

#include <iostream>
    #include <string>
    
    using namespace std;
    const int N = 1e6+5;
    int pNext[N];
    void getNext(string p,int len)
    {
        
        int j,i;
        i = 1,j = 0;
        while(i < len)
        {
        
            if(p[i] == p[j])
            {
        
                pNext[i] = ++j;
                i++;
            }
            else
            {
        
                if(j > 0)
                    j = pNext[j-1];
                else
                    pNext[i++] = 0;
            }
        }
    }
    void KMP(string s,string p,int lenp)
    {
        
        int i,j;
        i = j = 0;
        int lens = s.length();
        while(i < lens)
        {
        
            if(s[i] == p[j])
            {
        
                i++;
                j++;
            }
            else
            {
        
                if(j > 0) j = pNext[j-1];
                else i++;
            }
            if(j == lenp)
            {
        
                int pos = i - lenp + 1;
                /*
                * 匹配成功后继续匹配：
                * j从0开始的，j==lenp时，
                * j已经超出模式串p的范围，
                * 虚拟模式串s[j]有元素，此时肯定失配，则：j = next[j-1]
                */
                j = pNext[j-1]; 
                cout<<pos<<endl;
            }
        }
    }
    int main()
    {
        
        string s,p;
        cin>>s>>p;
        int lenp = p.length();
        getNext(p,lenp);
        KMP(s,p,lenp);
        cout<<pNext[0];
        for(int i = 1; i < lenp; ++i)
        {
        
            cout<<" "<<pNext[i];
        }
        cout<<endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/398fe506e8964ee79995f7475a9b4cf6.png
[P3375 _KMP]: https://www.luogu.com.cn/problem/P3375