kmp算法

字符串匹配

在字符串a中查找字符串b，b就是模式串。朴素算法是在a中遍历起始位置，一个一个字符比较，不匹配时起始位置往后移动一下。

KMP算法的失配处理的个人理解

讨论基于字符串下标从1开始。
KMP的想法则是：
$a[i],b[j]$不匹配了。此时已经可以确定的信息是不匹配位置前面的$j?1$个字符都是一样的,即$b[1,j?1]=a[i+1?j,i?1]$.
记$b[1,j?1]$这个子串为$s$。

• $j=1$,s是个空串，显然只能将模式串b往后移动1格。
• $j>1$,s非空。那$b$字符串往后移动$c$格，只要$1<c<=len(s)=j?1$,就相当于是$s$的前$k=len(s)?c$个字符和后$k$个字符在比较,一样的情况下，才会接着比较$b[k+\mathrm{1..}]$与$a[i..]$。显然移动的步子越小，$k$越大。可能有多个$k(k<len(s))$满足以下条件： s的前k个字符组成的子串和后k个字符组成的子串相等
  为了不遗漏可能的匹配，我们应该移动尽可能的少，即找尽可能大的$k$.
  这些满足前后子串相等的一系列$k$中，假设最大的是$K$，对应的移动步数是$C$,显然移动步数小于$C$的时候，$b$一定会不匹配，我们直接跳过这些移动步数不会造成遗漏。因此，当失配（$a[i]\ne b[j]$）时，我们可以直接移动$C$步。此时$b$的前$K$个字符和$a[i]$前面的$K$字符匹配上了，即$b[\mathrm{1..}K]=a[i+1?K,i]$，只需要从$b[K+\mathrm{1..}]$和$a[i..]$接着尝试匹配即可。 此时的情况和开始的情况是相似的，只是j换成了K。并且$K<j$,也就是说规模在缩小。
  next(s) s是一个字符串定义为满足s前k个字符组成的真子串和后k个字符组成的真子串相等的最大k.
  而当模式串b固定的情况下，next(j) j是整数定义为next(b[1..j])。
  有了$next(j)$的定义后，我们记$move(j)=j?next(j)$。$move(j)$的含义就是可以解释为至少移动一步的情况下，并且移动之后可以直接从a[i]开始尝试匹配，移动步数要尽可能少的最小移动步数。换句话说，移动步数小于$move(j)$的情况下，还没比较到$a[i]$就失配了。

KMP算法

有了上面的理解，KMP的匹配算法就容易描述了：

1. 初始化$i=1,j=1$
2. 尝试匹配：若$i>L_a$,则结束; 否则尝试比较$a[i],b[j]$
3. 若相等，则各自加1,$i=i+1,j=j+1$。
   1. $j>L_b$，说明已经完全匹配了，可直接计算出完全匹配的起始下标(在字符串a中)。为了寻找后续的匹配位置，并且不遗漏答案，此时应移动尽可能少的步数去尝试寻找后续的匹配位置。并且移动之后需要可以直接从a[i]开始尝试匹配，因此移动$move(j?1)$步（小于这个步数必然失配），所以直接更新$j=next(j?1)+1$. 回到步骤2接着尝试匹配；
   2. $j\le L_b$,模式串还未完全匹配,回到步骤2；
4. 若不等，说明失配，得移动。
   1. 如果第一个字符就失配了，即$j=1$，显然这种情况失配必须将模式串往后移动一格重新从模式串的第一个开始匹配，因此$i=i+1$; 回到步骤2接着尝试匹配。
   2. 如果$j>1$,需要尽可能少的移动，并且移动后可以直接从a[i]开始匹配。显然可以直接移动$move(j?1)$步，即更新$j=next(j?1)+1$. 回到步骤2接着尝试匹配。

虽然上面讨论看起来分了四种情况，但是，实际上代码可以很简单。
另外，需要注意的是情况3.2和情况4.2使用的都是已匹配串的next值。

刚刚说的是KMP的算法的$next(j)$的含义。那么如何求$next(j)$呢?
朴素的做法自然是根据定义，逐一验证$k=j?1,j?2,?,0$前后子串是否相等了。单个$next(j)$时间复杂度最坏情况下是$O(j^2)$.所有的则需要$O(l^3)$.

next数组的求取

$next(j)$与$next(j?1)$的关系

结论1 $next(j?1)\ge next(j)?1$.
证明：记$next(j)=d$,则
$$\begin{gathered} next(j)=d?b[\mathrm{1..}d]=b[j+1?d,j]? \\ b[\mathrm{1..}d?1]=b[j+1?d,j?1]?next(j?1)\ge d?1=next(j)?1 \end{gathered}$$.
人话解释就是，对于前$j$个字符构成的子串$b[\mathrm{1..}j]$前后相等的一个子串截取方案，只要都前后两个子串都去掉子串的最后一个字符，就是$b[\mathrm{1..}j?1]$的前后相等的方案，因此，$next(j?1)$至少是$next(j)?1$.

---

有了这个结论，我们就可以将$next(j)$的取值范围缩小到$next(j?1)+1$以内了，并且由$next(j)$的定义知，$b[\mathrm{1..}next(j?1)]=b[j?next(c),j?1]$
现在考虑如下的子问题：

子问题

子问题: 假设已知$next(j)\le c+1(c\ge 0)$，且$b[\mathrm{1..}c]=b[j?c,j?1]$。求$next(j)$的问题记作$f(c,j)$

1. 若$c=0$，说明$next(j)\le 1$,$b[\mathrm{1..}c],b[j?c,j?1]$是两个空串。此时只要比较$b[j]$和$b[1]$.
   1. 相等:$next(j)=1$
   2. 不等:$next(j)=0$
2. 若$c>0$,比较$b[j],b[c+1]$.
   1. 相等，则$b[\mathrm{1..}c+1]=b[j+1?c,j]$,易知$next(j)=c+1$.
   2. 不等，说明$next(j)\ne c+1$,因此可以知道$next(j)<c+1$.
      因此，问题转化成求一个尽可能大的$d(d<c)$,满足$b[\mathrm{1..}d+1]=b[j?d,j]$. $b[\mathrm{1..}d+1]=b[j?d,j]$可以拆分成两个条件:①$b[\mathrm{1..}d]=b[j?d,j?1]$ ②$b[d+1]=b[j]$.
      对于条件①，因为$b[\mathrm{1..}c]=b[j?c,j?1]$,所以取更短($d<c$)的区间有$b[j?d,j?1]=b[c+1?d,c]$，即条件①可以等价于③$b[1,d]=b[c+1?d,c]$。根据前面所述的$next(?)$的定义，显然只要$next(c)<d<c$，肯定不满足条件③。
      因此可以进一步缩小$next(j)$范围为：$next(j)=max(d)+1\le next(c)+1$}, 并且显然有$b[\mathrm{1..}next(c)]=b[j?next(c),j?1]$。\
      注意：此时，此时问题已经和原问题相似的子问题了，唯一的不同是$c$变成了$next(c)$。即转化为了问题$f(next(c),j)$. 由于$next(c)<c$，所以问题规模一直在缩小。
      由上面的叙述，得到了
      $$f(c,j)=?\begin{array}{rlr}0& c=0,b[j]\ne b[c+1];& (1)\\ 1& c=0,b[j]=b[1];& (2)\\ c+1& c>0,b[j]=b[c];& (3)\\ f(next(c),j)& c>0,b[j]\ne b[c];& (4)\end{array}=?\begin{array}{rlr}0& c=0,b[j]\ne b[c+1];& (1)\\ c+1& b[j]=b[c+1];& (2,3)\\ f(next(c),j)& c>0,b[j]\ne b[c+1];& (4)\end{array}$$
      其中case 2也符合case 4的表达式，因此可以合并。

$c$的初值的确定

所以就剩下一个问题，$next(j)=f(c,j)$中的最开始的$c$值该怎么确定呢？由结论1知$next(j)\le next(j?1)$，，恰好符合了$f$问题的已知(预设)，因此$next(j)=f(next(j?1),j)(j>1)$.
于是只余下边界$next(1)$的问题了。根据定义不难知道$next(1)=0$.

小结

$$next(j)=\{\begin{array}{rlr}0& j=1& (1)\\ f(next(j?1),j)& j>1& (2)\end{array}f(c,j)=?\begin{array}{rlr}0& c=0,b[j]\ne b[c+1];& (1)\\ c+1& b[j]=b[c+1];& (2,3)\\ f(next(c),j)& c>0,b[j]\ne b[c+1];& (4)\end{array}$$

因为c++数组下标是从0开始的，我们可以对next,f的定义稍作修改：

下标从1开始：$next(j)$为使得$b[\mathrm{1..}j]$子串中使得$b[\mathrm{1..}k]=b[j+1?k,j](k<j)$的最大$k$. $k$是前后相等子串的长度。 定义域是$[1,L_b]$
下标从0开始：$next(j)$为使得$b[\mathrm{0..}j]$子串中使得$b[\mathrm{0..}k?1]=b[j+1?k,j](k<j)$的最大$k$. $k$是前后相等子串的长度。 定义域是$[0,L_b?1]$
从1开始计数的$next[j]$就是$b[\mathrm{1..}j]$这个字符串的长度，而从0开始的$next[j]$则是$b[\mathrm{0..}j]$的长度减1.

下标从1开始：$f(c,j)$：已知$next(j)\le c+1(c\ge 0)$，且$b[\mathrm{1..}c]=b[j?c,j?1]$。求$next(j)$
下标从0开始：$f(c,j)$：已知$next(j)\le c+1(c\ge 0)$，且$b[\mathrm{0..}c?1]=b[j?c,j?1]$。求$next(j)$

那么下标从0开始：
$$next(j)=\{\begin{array}{rlr}0& j=0& (1)\\ f(next(j?1),j)& j>0& (2)\end{array}f(c,j)=?\begin{array}{rlr}0& c=0,b[j]\ne b[c];& (1)\\ c+1& b[j]=b[c];& (2,3)\\ f(next(c?1),j)& c>0,b[j]\ne b[c];& (4)\end{array}$$
匹配的时候，不管下标从0还是1开始计数，不管是失配了需要移动还是已经完全匹配了需要移动找下一个可能的匹配的位置。最少的移动的步数都是$L_{matched\_str}?next(matched\_str)$。小于这个移动步数则必然会失配，而采取这个移动步数，就会使得移动后模式串的前$next(matched\_str)$个字符是匹配的，而$j$作为下标，只需要根据长度基于0还是1去计算了。

Code

因此，不难得到$next$数组的求解代码(下标从0开始)：

// 下标从0开始计数，nxt[j](0 <= j < n)含义是针对s[0..j]的前后真子串相等的最长长度.
// n是s的长度。
void cal_nxt(char *s, int n) {
    nxt[0] = 0;
    for (int i = 1;i < n; i++) {
        int c = nxt[i-1];
        while (c>0 && s[i] != s[c]) c = nxt[c-1];
        if (s[i] == s[c]) nxt[i] = c+1; else nxt[i] = 0;
    }
}

匹配

// b是模式串，a是文本串。需要在a中找所有b出现的其实位置
int j = 0; // 模式串下标小于j前面的都已经匹配成功了；当下标从0开始计数的时候，j就是已经匹配的长度。
for (int i = 1;i < n; i++) {
    while (a[i] != b[j] && j > 0) j = nxt[j-1]; // 只要失配，并且已经匹配的长度大于0，就可以更新为已经匹配串的next
    if (a[i] != b[j]) continue; // 说明是第一个位置失配了，只能是起始位置往后移动
    ++j; // 匹配成功了，后移
    if (j == m) { // 完全匹配了
        // b在a中出现的起始下标
        cout<<i+2-m<<"\n";
        j = nxt[j-1]; // 已匹配串的nxt
    }
}