next数组计算方法如下

默认next[0]=-1，字符串从0出发。

计算的方法是：

1
2
3
4
5

int j = 0, k = -1;
while(j < p.size() - 1) {
    if(k == -1 || p[j] == p[k]) next[++j] = ++k;
    else k = next[k];
}

其中p是模式串。

接下来我们来推导KMP的状态转移方程。

设$dp[j]$是第j处最大公共真前后缀的长度，那么如果$p[j]==p[k]$，那必然有$dp[j+1]=dp[j]+1=k+1$（可以想象一下，后面一位字符也是相等的，那就说明这里的最大公共真前后缀的长度等于前一位的+1嘛！），并且j和k都递增一次。

哈希函数是指将任何一种类型的变量$x$映射到$hash(x)$里，其中$hash(x)$是比较小的数值。一般来说，我们希望这种函数是一对一的，但偶尔会出现哈希碰撞的情况，即一对多的情况。这种情况是不可取的。

很多情况下，我们都将字符串的起始下标设为1.

在这里，$hash(i)$表示从1到下标$i$这个字符串的哈希值。所以我们要先确定前缀字符串，比如给定：

那么$hash(0)=hash(“A”)，hash(1)=hash(“AB”)…$

在计算的时候，我们把字符串当作$p$进制数，并按照ASCII码赋值，其hash函数就是将$p$进制数转换成10进制数。因此：