复习了一下KMP。与其说是复习，不如说是重学了一遍。

学习KMP实际上就是学习了前缀函数。下文大抵把OI-Wiki上关于前缀函数和KMP的部分内容说了一下。

前缀函数

定义

给定一字符串，对于它的每个前缀\(s[0,i-1]\)，存在该子串的真前缀与真后缀相同，其中最大的一对前后缀的长度，记作：

特别地，约定\(\pi[0]=0\)。
如字符串s="abcdabc"，它的前缀函数如下：
\(\pi[1]=0,\pi[2]=0,\pi[3]=0,\pi[4]=0\)

\(\pi[5]=1\)，因为子串abcda中，\(s[0,0]==s[4,4]\)

\(\pi[6]=2\)，因为子串abcdab中，\(s[0,1]==s[4,5]\)

\(\pi[7]=3\)，因为子串abcdabc中，\(s[0,2]==s[4,6]\)

因此\(s\)的前缀函数为：\([0,0,0,0,1,2,3]\)

注意 在某字符串\(s\)中，相等的前后缀形如abc和abc，不是abc和cba（虽然没有人会像我一样弄错）

求前缀函数

枚举

首先可以想到枚举。

求字符串\(s\)的每一个前缀\(s[0,i-1]\)的前缀函数值，从\(i-1\)开始枚举前后缀长度\(j\)，一项一项判断它们是否相等。

复杂度\(O(n^3)\)，显然在数据范围较大时会超时。

优化

注意到\(\pi[i]\)最多只会比\(\pi[i-1]\)多1，因此从\(\pi[i-1]+1\)开始枚举前后缀长度\(j\)。

复杂度\(O(n^2)\)，虽然快了但是在数据范围较大时还是会超时。

继续优化

如果当\(j=\pi[i-1]+1\)时匹配成功那当然是最优的，现在的问题是如果匹配失败该怎么办。

注意到我们在上述枚举过程中浪费了很多时间去枚举不相等的前后缀的长度。

如图所示，当s=abcabdeabcabc（精心设计的字符串），\(i=13\)时，我们可以看到：

首先，令\(j=\pi[i-1]+1\)，即\(j=6\)，显然前缀abcabd不等于后缀 abcabc；

然后，令\(j=5\)，更显然前缀abcab不等于后缀bcabc；

然后，令\(j=4\)，更显然前缀abca不等于后缀cabc；

然后，令\(j=3\)，此时前缀abc等于后缀abc，匹配成功，\(\pi[13]=3\)。

我们可以看到，当\(j=5\)和\(4\)时，显然前后缀不可能相等。但是\(j=3\)时前后缀有可能相等，最终确实相等。

那么\(j=3\)有什么特点呢？我们可以注意到\(3=\pi[\pi[i-1]-1]+1\)。

也就是说，在读入新的字符时，如果第一次匹配失败，我们可以直接枚举第二长的前后缀，即令\(j=\pi[\pi[i-1]]+1\)，其余情况，因为读入前这段前后缀就不相等，读入后，前后各加入一个字符，自然不可能相等。

于是我们就能得到一个状态转移方程：\(j[n]=\pi[j[n-1]-1]\)

实现

像这样：

std::vector<int> prefixFunction(std::string s)
{
    std::vector<int> pi(s.size());
    pi[0]=0;
    for(int i=1;i<=s.size();i++)
    {
        int j=pi[i-1];
        while(j>0&&s[i]!=s[j])
            j=pi[j-1];
       	if(s[i]==s[j])
            j++;
     	pi[i]=j;
    }
    return pi;
}

KMP

就是前缀函数的一种应用，用于求解形如“求字符串\(s1\)在\(s2\)中出现了几次，每次出现的位置”这类问题。

把\(s1\)接在\(s2\)前面，中间加一个字符集之外的字符（如：\(s1\)、\(s2\)均由小写字母组成的，可以加入一个大写字母，虽然笔者不建议这样做），然后求它的前缀函数。

P3375 【模板】KMP

当前缀函数值为\(len(s1)\)时，此时的位置\(i\)就是\(s2\)中出现一次\(s1\)的末位置。\(s2\)中这次出现\(s1\)的初位置，就是\(i-2len(s1)\)。

由于这篇文章说的是KMP，所以前缀函数其他应用就先不写了。