课程地址：https://www.icourse163.org/course/ZJU-93001
笔记中图片均来自此mooc中讲义。

之前发现新的课程中补充了KMP算法，这里做下回顾。

串的模式匹配

串的模式匹配是找在文本中找到某个模式第一次出现的位置：

这里讨论的一般为字符串，设文本的长度为$n$，模式的长度为$m$，下面看下处理的方法。

蛮力算法

最基本的思路是蛮力算法，即让模式的头指针遍历文本的每个位置，然后比较后续对应位置的元素，不难看出，时间复杂度为$O(nm)$，这种时间复杂度是很难让人接受的，幸运的是，有人给出了KMP算法。

KMP算法

蛮力算法中模式的头指针一次只移动一个位置，那么这种操作能否改进呢？回答是肯定的，来看下面的例子：

为了讨论方便，这里引进两个新的变量$s,p$，$s$为文本当前匹配位置，$p$为模式当前匹配位置，通过移动$s,p$来进行匹配操作。图中$s$指向$x$，$p$指向$c$，因为$c\neq x$，所以指针要移动，蛮力算法是将$s$回退到第一个$b$的位置，$p$回退到模式的头指针位置，但是我们观察上图不难发现pattern的头部$ab$和$p$之前两位相同，所以我们可以保持$s$不动，将$p$指向第一个$c$的位置，于是就变为第三行的情形。这个例子提醒我们要先对模式串的模式进行分析，于是有了如下match数组：

有了match数组之后，匹配不成功回退的位置就可以知道了，令$i=\text{match}[p-1]$，那么$a_{0}…a_{i}$和$a_{p-i-1}…a_{p-1}$相同，所以$p$回退到$\text{match}[p-1]+1$的位置，可以结合下图看：

于是有了如下的算法：

typedef int Position;
#define NotFound -1

Position KMP( char *string, char *pattern )
{
    //计算长度
    int n = strlen(string);
    int m = strlen(pattern);
    Position s, p, *match;
     
    //文本长度小于模式长度显然无法匹配
    if ( n < m ) return NotFound;
    match = (Position *)malloc(sizeof(Position) * m);
    //构造match数组
    BuildMatch(pattern, match);
    //初始化指针
    s = p = 0;
    while ( s<n && p<m ) {
        if ( string[s]==pattern[p] ) {
            s++; p++;//相同则同时往后移动一位
        }
        else if (p>0) p = match[p-1]+1;//不相同且p不是头指针则回退
        else s++;//否则s往后移动一个位置
    }
    return ( p==m )? (s-m) : NotFound;//p走到m表示匹配，返回其在文本中的位置，否则返回不匹配
}

接下来分析时间复杂度，计算长度的时间复杂度为$O(n+m)$，BuildMatch的时间复杂度暂时未知，设为$T_m$，最后循环的时间复杂度为$O(n+m)$，总的时间复杂度为$O(n+m+T_m)$，所以接下来的问题为如何快速BuildMatch

BuildMatch

BuildMatch相当于串的自匹配，结合下图讲解：

假设指针为$j$，令$i=\text{match}[j-1]$，那么$b_{0}…b_{i}$和$b_{j-i-1}…b_{j-1}$相同并且这种匹配是最大匹配，如果$b[i+1]$和$b[j]$相同，显然有

如果不同，则再往前回退，如下图：

不难看出$i$应该回退到$\text{match}[i]$的位置，然后继续比较$b[i+1]$和$b[j]$，继续回退直至相同或者无法回退为止，于是有了如下算法：

void BuildMatch( char *pattern, int *match )
{
    Position i, j;
    int m = strlen(pattern);
    match[0] = -1;
     
    for ( j=1; j<m; j++ ) {
        i = match[j-1];
        while ( (i>=0) && (pattern[i+1]!=pattern[j]) )
            i = match[i];//能回退且不相同则一直回退
        if ( pattern[i+1]==pattern[j] )
             match[j] = i+1;//相同则更新match
        else match[j] = -1;//不能回退且不相同则为-1
    }
}

接下来分析时间复杂度，老师讲解部分没有太听明白，查阅了网上资料，给出一个自己的分析过程。

不难看出，我们最主要分析的量为回退次数，假设$T[i]$为计算$\text{match}[i]$回退的次数，每次回退，$\text{match}[i]$至少减$1$，所以有如下不等式：

备注：注意一开始的赋值为

每次回退至少减少$1$，$T[i]$次回退至少减少$T[i]$，所以得到上述条件。

现在利用上述结论分析时间复杂度，计算长度的时间复杂度为$O(m)$，一共循环$m$次，每次最多增加$1$，总共最多回退$m$次，所以循环总共的时间复杂度为$O(m)$，因此BuildMatch的时间复杂度为$O(m)$，即$T_m =O(m)$，从而KMP算法的时间复杂度为$O(m+n)$