算法简介：巡护深林

KMP 算法，虽然我们已经在【算法介绍】字符串算法 | 祝馀宫中提及，但是现在有了更深的理解，我们这篇文章单独讲 KMP 算法以及其原理。~~为了凑字数，我们再讲一遍废话。~~ KMP 算法，全称 $Knuth-Morris-Pratt$ 算法，通过一种特殊的性质匹配两个字符串，从而达到减少匹配次数的算法。

算法演示：漫行山薮

变量定义：夏堇芳菲

我们对于接下来的一些内容做出如下定义：

名称	定义
子串	~~不用多说了罢~~，在字符串中截取任意一段连续的内容，被称为子串下文用 $s[l\dots r]$ 表示字符串 $s$ 的从 $l$ 到 $r$ 的这部分子串。下文所有关于字符串的计算都是以 1 为开始的下标*
子序列	不要求连续，但是在原字符串中内容顺序相同的字符串。
前缀子串	一个字符串的前缀组成的子串，表示为 $pre(s,i)=s[1\dots i]$ ，即 $s$ 字符串长度为 $i$ 的前缀
后缀子串	一个字符串的后缀组成的子串，表示为 $suf(s, i) = s[n-i+1\dots n]$ ，即 $s$ 字符串长度为 $i$ 的后缀
最长公共前缀	两个字符串最长的公共前缀，记作 $lcp(s,t)$
最长公共后缀	两个字符串最长的公共前缀，记作 $lcs(s,t)$
周期	我们称一个字符串 $s$ 的周期长度为 $p$ 当且仅当对于所有的 $i$ ，$s_i=s_{i+p}\ \ (i+p\le len(s),0\lt p\lt len(s))$ 这里 $p$ 取不到 $len(s)$ 的原因是因为一个字符串的周期不能是他本身
$\tt Border$	对于一个长度 $p$ 满足 $pre(s,p) = suf(s,p)$ 的子串，被称为字符串 $s$ 的 $\tt border$ 。
模式串	被匹配的
匹配串	与模式串进行匹配的

如果我们已知一个 border 那么如何确定一个字符串的周期呢？我们用下图来表示两种可能的 border 及其周期对应。

这种的 border 周期性很明显，因为周期如果是超出了原来的字符串，他就不算了，所以我们显然可以做出一个周期，他从前缀 border 的左端点开始，一直到后缀 border 的左端点，这样就可以构造出一个正确的周期，显而易见是比较显然的。

这个 border 的周期显而易见，就是前缀 border 和后缀 border 岔开来的那一段，因为这一段作为前缀 border 的前一段，肯定和后缀 border 的那一段是一样的，又因为这一段是对其前缀 border 的后面那一段，然后她肯定也等于后缀 border 的后一段。这样也是一个周期的。

算法推导：骞林馈遗

首先，我们~~按照惯例~~来看看纯暴力的做法。显而易见的，纯暴力就是大力的枚举这个匹配串在模式串开始匹配的起点，然后大力匹配，总复杂度 $O(nm)$ 代码如下

for(int i = 1; i + lent <= lens; i++) {
    int flag = 1;
    for(int j = 1; j <= lent; j++) {
        if(s[i + j - 1] != t[j]) {
            flag = 0; break;
        }
    }
    if(flag) {
        printf("YES");
        return ;
    }
}

显而易见的，这个算法的瓶颈在于过多次的无效匹配。那么我们就要想，如何去减少无效匹配的次数。最直观的方式，就是保证我们目前跳到的下一个匹配点的已知部分都是和这个目前的最大匹配点是一样的。那么我们最容易想到的是不是我们上面提到的 border ？我们想一想对于匹配的定义，如果我们存在两个指针 $i,j$ 分别指向模式串 $s$ 和匹配串 $t$ 。那么当前的匹配一定满足 $s[i-j+1] = t[j]$ 。也就是说，对于我们当前匹配到的这一段，始终是模式串 $s$ 的一个长度为 $j$ 的子串，匹配串 $t$ 的一个前缀，由于我们要减少无效匹配的次数，所以我们就要保证当前匹配失败的点，在重新移动后的这一段任然是不变的，那么就满足 border 的条件，并且为了减少过度跳跃导致的漏掉匹配，我们每次只需要跳到最长 border 的位置。

那么现在的问题就是如何求一个真前缀子串的最长 border 。这里我们就引入一个数组 $nxt$ 数组，他表示子串 $s[1\dots i]$ 的最长 border 长度。那么我们考虑如何去求他。用动态规划的思想去思考的话，我们一定是从某一个 border 延长而来。那么根据 border 的传递性，我们只要一直的让指针 $j=nxt[j]$ 就可以了，然后比对每一个 border 之后的那一个字符是不是一样的，也就是满不满足延长条件，就可以了。

void Getnxt() {
    nxt[1] = 0; int j = nxt[1];
    for(int i = 2; i <= n; i++) {
        while(j && t[i] != t[j + 1]) j = nxt[j];
        if(t[i] == t[j + 1]) j++;
        nxt[j] = j;
    }
}

那么细心的人已经注意到我们这个 $nxt$ 数组是对于匹配串而不是模式串匹配的了。因为 $nxt$ 是真前缀子串的最长 border 而处于匹配中的模式串并不满足这个要求，所以目光转向匹配串，移动他，就可以了。那么有了这个，其实 KMP 的代码绝对不会难写，和求 $nxt$ 很像，不停的跳指针就可以了。

int j = 0;
for(int i = 1; i <= lens; i++) {
    while(j && s[i] != t[j + 1]) j = nxt[j];
    if(s[i] == t[j + 1]) j++;
    if(j == lent) {
        printf("YES");
        return ;
    }
}