这次一定要学会KMP

概述

KMP是一种快速的字符串匹配算法，字符串匹配的暴力做法中，当匹配到某一个字符时失配，模式串需要重新回到第一个字符串，对应的，主串需要在上一个起点的基础上前进一个字符，而KMP解决的问题就在这里，通过预处理，在这里可以让模式串跳多个字符，从而加快匹配速度，最终时间复杂度是O(n+m)，n是主串长度，m是模式串长度，其中预处理复杂度是O(m)，匹配复杂度是O(n)。

首先计算一个nex数组(也有叫做fail函数，意思相同，指匹配失败之后的处理)，简单来说，nex[i]表示模式串前缀pat[0…i]的最长相同前后缀长度(可重叠，但不可以是整个子串)，这里也有另一种表示法，nex[0]为-1，然后用nex[i]表示前i的字符，也就是模式串前缀pat[0…i-1]的最长相同前后缀长度。

匹配

思路

先不考虑nex数组的计算，直接考虑匹配，假设采用的是第二种表示方法，也就是nex[i]表示模式串前i个字符的最长相同前缀后缀长度，那么，现在假设匹配到第8个字符串(i=7)失配了，按照上一节提到的，原串不动，模式串跳多个字符，那么跳多少呢，就得看此时的nex值，nex[7]表示此时模式串前7个字符的最长相同前缀后缀长度，注意这7个字符是和原串匹配的，所以如果nex[7]=3，大概就是abcdabc这种情况，那么原串的前7个字符也是abcdabc，这时候，很显然，我们把模式串跳到原串的第5个字符，也就是第二段abc开始匹配，就可以节省很多没必要的移动了，这里跳的数量就是i-nex[i]。

代码

// kmp基本查找有几种：查找出现位置(第一次/多次)，查找数量(可重叠/不可重叠)
int kmp(char* s,int n,char* p,int m){
    kmp_pre(p,m);
    // i，j分别是主串和模式串比较字符下标
    int i=0;
    int j=0;
    while(i<n && j<m){
        printf("%d %d\n",i,j);
        // 这里j=-1表示没有相同前后缀了，所以实际上应该是i++;j=0;只是这里合并了分支
        if(j==-1 || s[i]==p[j]){
            i++;
            j++;
        }else{
            j=nex[j];
        }
        // 匹配个数
        // if(j==m){
           // 统计数量，多次出现的位置同理
           // cnt++;
           // 可重叠
           // j=nex[j];
           // 不可重叠
           // j=0;
        // }
    }
    // 匹配
    if(j==m){
        // 返回第一个出现位置
        return i-j;
    }
    return -1;
}

预处理

思路

解决了匹配，剩下的就是如何求出nex数组，有两种情况。

第一种，比如abaabaabaabaa，我们已经求出了nex[12]=9，要求nex[13]，就需要比较pat[12]和pat[9]，这里两个字符相等，都是a，刚好可以接上，所以nex[13]=nex[12]+1。

第二种，比如bacababacabac，我们已经求出了nex[12]=6，要求nex[13]，同样需要比较pat[12]和pat[6]，这里字符c和b是不相等的，那说明我们无法直接接上nex[12]对应的前缀pat[0…5]，所以我们尝试把前缀缩短，缩短有个重要的前提，我们必须保证我们的字符pat[12]能够接上后缀，因此我们并不是把前缀从pat[0…5]缩短到pat[0…4]，我们需要保证缩短后的前缀pat[0…k]和pat[12]之前的某一段子串是相同的，所以我们直接跳到nex[6]即可(文字解释非常无力)，比如bacababacabac，一开始我们尝试pat[12]和后缀pat[6…11]拼接，拼接失败，因为pat[12]不等于pat[6]，所以前缀pat[0…5]不能延伸作为nex[13]，我们考虑缩短到，根据nex[6]=2，我们将前缀缩短到pat[0..1]，此时pat[12]要拼接的后缀对应的就是pat[10…11]，拼接成功，所以nex[13]=2+1=3，总之就是抓住nex数组的定义，前缀和后缀相同，那么前缀的前缀(特指nex数组对应的最大相同前缀，后缀同理)和后缀的后缀也相同，不断尝试拼接后缀，直到可以拼接上或者nex值为-1。

一个类似于并查集路径压缩的小优化：比如模式串是abab，主串是abacababc，当匹配到s[3]和p[3]，失配，模式串向右移动两位，然后比较s[3]和p[1]，但是实际上这两个肯定失配，因为从模式串abab来看，当某一个字符p[i]失配，下一个要匹配的字符肯定是p[nex[i]]，而对于这个模式串的p[3]，p[3]=p[nex[3]]，所以显然失配，为了避免这些无谓的比较，采用一种类似压缩路径的方法，当计算nex[3]时，也就是即将nex[++i]=++j，i是当前比较字符，j是前缀长度，我们继续看下一个字符，也就是p[3]，如果p[3]=p[j]，那么我们就要避免nex[++i]=nex[++j]的出现，而是使用nex[++i]=nex[++j]，这里可以这么写是因为nex[++j]已经在之前迭代求出来，所以这相当于一个非递归的路径压缩，这样子当失配的时候，因为nex[3]是-1了，所以模式串不再是右移到p[1]。

代码

代码乍一看和思路不太一样，其实是经过了一些写法上的优化。

void kmp_pre(char* p,int m){
    // i初始化为0表示要比较的字符，也就是要求nex[i+1]
    int i=0;
    // j表示尝试拼接的后缀长度(也等于前缀长度)，所以也是要比较的字符下标
    // 初始化为-1，因为一开始前缀为空
    int j=-1;
    nex[0]=-1;
    while(i<m){
        // j==-1只有可能是前缀为p[0]，此时nex值为0，合并分支
        if(j==-1 || p[i]==p[j]){
            // 因为要求的是nex[i+1]，之后求下一个，所以是++i
            // j是前缀长度，拼接上所以是j+1
            if(p[i+1]==p[j+1]){
                // 优化
                nex[++i]=nex[++j];
            }else{
                nex[++i]=++j;
            }
        }else{
            j=nex[j];
        }
    }
}

拓展

周期和border

来源金策的字符串ppt，省去其中看起来比较复杂的定义。

border其实就是字符串的相同前后缀长度，所以nex数组其实求的就是前缀的最长border。

周期是子串的长度，且该可以通过重复构成原串(可能不是完整的)。

比如abaaaba，周期是4(abaa)，6(abaaab)，7(abaaaba)，border是aba，a和空串。