KMP基础理解

我们要理解KMP，首先我们要理解KMP的功能是什么？

    假设我要你去完成一个搜索问题，给你两个字符串，一个模板S（adaaaadaafafgag）和一个P(ad),
 然后你去匹配S与P,获取P在S中相同字符串的首字母检索值。答案有可能不唯一，我们实现可以     
 想到暴力枚举匹配，用两重循环其时间复杂度为O(m*n),当然我们也可以用专门为这个问题设计     
 的算法/字符串查找算法（KMP）.
   它可以对P建立一个next数组O(m)，然后在与S匹配，所以他的时间复杂度就是O（m+n）。

KMP:
   Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串S内查找一个词W的出现位置。
   此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重
   新检查先前匹配的字符。

   它可以优化暴力枚举做法，将时间复杂度有O（m*n）降到O(m+n),所以我们有暴力枚举做法的基础。接下来
   我们看一下暴力枚举，和怎么用kmp去优化？

暴力枚举

让我们用一个实例来演示这个算法。在任意给定时间，本算法被两个整数m和i所决定：

m代表主文字符串S内匹配字符串W的当前查找位置，
i代表匹配字符串W当前做比较的字符位置。

图示如下：

             1         2  
m: 01234567890123456789012
S: ABCJABCDABFABCDABCDABDE
W: ABCDABD
i: 0123456

我们从W与S的开头比较起。我们比对到S[3]时，发现W[3]与其不符。
接着并不是从S[1]比较下去。我们已经知道S[1]~S[3]不与W[0]相合。因此，略过
这些字符，令m = 4以及i = 0。

             1         2  
m: 01234567890123456789012
S: ABCJABCDABFABCDABCDABDE
W:     ABCDABD
i:     0123456

如上所示，我们检核了”ABCDAB”这个字符串。然而，这与目标仍有些差异。我们可以
注意到，”AB”在字符串头尾处出现了两次。这意味着尾端的”AB”可以作为下次比较的
起始点。因此，我们令m = 8, i = 2，继续比较。图标如下：

             1         2  
m: 01234567890123456789012
S: ABCJABCDABFABCDABCDABDE
W:         ABCDABD
i:         0123456

于m = 10的地方，又出现不相符的情况。类似地，令 m = 11, i = 0继续比较：

             1         2  
m: 01234567890123456789012
S: ABCJABCDABFABCDABCDABDE
W:            ABCDABD
i:            0123456

这时，S[17]与W[6]相同，但是亦出现了两次”AB”，我们采取一贯的作法，
令m = 15和i = 2 ，继续搜索。

             1         2  
m: 01234567890123456789012
S: ABCJABCDABFABCDABCDABDE
W:                ABCDABD
i:                0123456

我们找到完全匹配的字符串了，其起始位置于S[15]的地方。

好了，说了怎么多，我们来看一下模拟该过程代码：

int search(int n,char *a,itn m,char *b )
//n,m分别为a,b的长度

{
    for(int i=0,j=0;i<n&&j<m;){
        //匹配过程
        if(s[i]=w[i]),i++,j++;
        //重新开始
        else i-=j-1,j=0;

    }
    if(j==m)return i-j;
    else return -1;
}

~~~好了，看了代码我们发现多次匹配S中的任何字符,对于W中的任何位置，我们都希望能够查询那个位置前（不包括那个位置）有可能的W的最长初始字段的长度，而不是从W[0]开始失配的整个字段，这长度就是我们查找下一个匹配时回退的距离。因此next[i]是W的可能的适当初始字段同时也是结束于W[i-1]的子串的最大长度。我们使空串长度是0。当一个失配出现在模式串的最开始，这是特殊情况（无法回退），我们设置next[0]=-1，在下面讨论。

KMP

我们首先考虑例子W=”ABCDABD”。使用这个大致相同模式串作为主搜索，我们将会看到它高效的原因。

首先，我们设定next[0]=-1。为了找到next[1]，我们必须找到一个”A”的适当后缀同时也是W的前缀。但”A”没有后缀，所以我们设定next[1] = 0。类似地，next[2] = 0。

继续到next[3]，我们注意到检查所有后缀有一个捷径：假设我们发现了一个适当后缀，结束于W[2]、长度为2（最大可能）的后缀，那么它的第一个字符是W的一个适当前缀。因此一个结束于W[1]的适当前缀，我们已经确定了不可能出现在next[2]。因此在每一层递推中，这个规则是只有在上一层找到一个长度为m的有效后缀时，才需要检查给定长度为m+1的后缀（例如，next[x]=m）。

那么我们甚至不需要关心具有长度为2的子串，由于上一个情况因长度为1而失配，所以next[3] = 0。

我们继续遍历到W[4]子序列，’A’。同样的逻辑说明我们需要考虑的最长子串的长度是1，并且在’A’这个情况中有效，回退到我们寻找的当前字符之前的字段，因此next[4] = 0。

现在考虑下一个字符W[5]，’B’，我们使用这样的逻辑：如果我们曾发现一个子模式在上一个字符W[4]之前出现，继续到当前字符W[5]，那么在它之前它本身会拥有一个结束于W[4]合适的初始段，与事实相反的是我们已经找到’A’是最早出现在结束于W[4]的合适字段。因此为了找到W[5]的终止串，我们不需要查看W[4]。因此next[5] = 1。

最后，我们看到W[4] = ‘A’下一个字符是’B’，并且这也确实是W[5]。此外，上面的相同参数说明为了查找W[6]的字段，我们不需要向前查看W[4]，所以我们得出next[6] = 2。

于是我们得到下面的表格：
i 0 1 2 3 4 5 6
W[i] A B C D A B D
ne[i] -1 0 0 0 0 1 2

（！！！！！）如果你认为这个解释太过于复杂，你可以这样理解例如ababa的前缀为a,ab,aba,abab， 后缀为 a, ba, aba, baba,前后缀都不包含自身那么匹配数组ne[0~4]为 0 0 1 2 3，ne[0] = 0表示没有前后缀（因为前后缀不包含自身），当然你也可以一设为-1，这里你理解这个过程。

我们还是画一个图理解一下：

好了，我们已经对p字符串的预处理已经完了，下面来看一下，如何去匹配他们，如上图所示：
我们来画一个图来理解一下：

好了理解了next[]数组的预处理，以及如何去匹配，我们来看一下模板代码：

模板

   求Next数组：
// s[]是模式串，p[]是模板串, n是s的长度，m是p的长度
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

习题

习题链接

题意

题意就是我们KMP算法要解决的问题：

AC代码：

#include<iostream>

using namespace std;

const int N=100010;
char a[N],b[N];
int ne[N];
int  n,m;

int main(){
    cin>>n>>a+1>>m>>b+1;
    for(int i=2,j=0;i<=n;i++){
       while(j&&a[i]!=a[j+1])j=ne[j];
       if(a[i]==a[j+1])j++;
       ne[i]=j;

    }
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&b[i]!=a[j+1])j=ne[j];
        if(b[i]==a[j+1])j++;
        if(j==n){
            cout<<i-n<<" ";
            j=ne[j];
        }
    }
    return 0;
}

小结

KMP算法就两个点，也就是如果待处理字符串求取next[]数组，二就是他们如何去检索的，如何随着j与next[j]的变化而去确定检索位置的，然会在匹配，就好了，重要的是求取next的用用意是什么？我们如何在优化代码节省时间的？谢谢你的阅读！希望你有所收获！

相关练习题

习题1
习题2
习题3

题解会在后面加上！

yxc老师的模板 链接

求Next数组：
// s[]是模式串，p[]是模板串, n是s的长度，m是p的长度
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

作者：yxc
链接：https://www.acwing.com/blog/content/404/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。